你的任务便是告诉 小Z ，他有多大的概率抽到两只颜色相同的袜子。当然， 小Z 希望这个概率尽量高，所以他可能会询问多个 (LR) 以方便自己选择。
N 为袜子的数量， M 为 小Z 所提的询问的数量。接下来一行包含 N 个正整数 Ci ，其中 Ci 表示第 i 只袜子的颜色，相同的颜色用相同的数字表示。区间任意挑选两个的组合数很简单，那剩下的问题便是该区间内有多少组相同的颜色。
于是我们可以使用莫队算法来解决这个问题啦~
每个区间可以抽象成平面中的点，每次转移的花费都相当于从某一点到另一点的曼哈顿距离，所以最好的做法便是在曼哈顿最小生成树上的转移啦。