CERN 是一个专注于核研究和粒子物理的国际机构。CERN 的粒子加速器系统用于进行涉及高速粒子碰撞的实验。
我们考虑 $N$ 个排列成序列的粒子。每个粒子由其类型 $v_i$ 定义，用 $1$ 到 $N$ 之间的正整数表示。
在最新的研究中，需要进行 $Q$ 次实验。在第 $i$ 次实验中，我们观察序列中从第 $l_i$ 个到第 $r_i$ 个的所有粒子（$l_i < r_i$）。在观察到的粒子中，我们可以选择任意两个不同类型的粒子并在加速器中使它们碰撞，导致这两个粒子都被销毁。只要观察到的粒子中还有两个不同类型的粒子，我们就重复这个碰撞过程。实验要么在所有观察到的粒子都被销毁时结束，要么在剩下一些相同类型的粒子时结束。当然，根据我们碰撞粒子的顺序，最终可能会剩下各种类型的粒子。
由于粒子碰撞成本高昂，你决定仅在理论上进行实验。现在，对于每次实验，你感兴趣的是：有多少种粒子类型，使得实验结束后有可能剩下该类型的粒子。
输入格式
第一行包含两个正整数 $N$ 和 $Q$，分别表示粒子的数量和实验的次数。
下一行包含一个长度为 $N$ 的序列 $v_1, \dots, v_N$，表示粒子的类型。
接下来的 $Q$ 行中，每行包含一对正整数 $l_i$ 和 $r_i$ ($1 \le l_i < r_i \le N$)，表示第 $i$ 次实验中观察到的粒子区间。
输出格式
对于每次实验，在单独的一行中输出使得实验结束后有可能剩下该类型的粒子数量。
子任务
在所有子任务中，$2 \le N \le 500,000$ 且 $1 \le Q \le 500,000$。
| 子任务 | 分值 | 数据范围 |
|---|---|---|
| 1 | 13 | 对于每个 $i=1, \dots, N$，$v_i \le 10$。 |
| 2 | 19 | 每种类型的粒子最多有两个。 |
| 3 | 17 | $N, Q \le 2000$ |
| 4 | 19 | $N, Q \le 100,000$ |
| 5 | 32 | 无附加限制。 |
样例
输入 1
11 5 2 4 2 3 4 4 3 1 4 4 4 1 4 2 8 6 9 8 10 8 11
输出 1
1 4 1 1 1
说明 1
在第一次实验中，我们可以碰撞类型为 3 和 4 的粒子，剩下两个类型为 2 的粒子。没有办法以任何其他类型的粒子结束。
在第二次实验中，有可能剩下每种类型的粒子。
在第四次和第五次实验中，无论如何选择碰撞，最终都会剩下一些类型为 4 的粒子。