题目背景

题目来源：https://hsin.hr/hio2024/。翻译来自 文心一言。如果有更好的翻译请在讨论区提供。

题目描述

CERN 是一个专注于核研究和粒子物理学的国际机构。CERN 的粒子加速器系统被用于进行高速粒子碰撞实验。

我们考虑按序列排列的 $N$ 个粒子。每个粒子由其类型 $v_i$ 定义，$v_i$ 是一个介于 $1$ 和 $N$ 之间的正整数。

在最新的研究中，需要进行 $Q$ 次实验。在第 $i$ 次实验中，我们观察序列中从第 $l$ 个到第 $r$ 个的所有粒子（其中 $l < r$）。在观察到的粒子中，我们可以选择任意两个类型不同的粒子并在加速器中进行碰撞，导致两个粒子都被摧毁。我们重复这个碰撞过程，直到观察到的粒子中没有两个类型不同的粒子为止。实验将在所有观察到的粒子都被摧毁或仅剩下同类型的粒子时结束。当然，根据我们碰撞粒子的顺序，最终可能留下各种类型的粒子。

由于粒子碰撞成本高昂，你决定只在理论上进行实验。现在，对于每次实验，你感兴趣的是有多少种类型的粒子，使得实验结束时可能剩下该类型的粒子。

输入格式

第一行包含两个正整数 $N$ 和 $Q$，分别表示粒子的数量和实验的次数。

第二行包含 $N$ 个数 $v_1, \dots, v_N$，表示粒子的类型。

接下来的 $Q$ 行中，每行包含两个正整数 $l$ 和 $r$（$1 \leq l < r \leq N$），表示第 $i$ 次实验中观察到的粒子区间。

输出格式

对于每次实验，在单独的一行中输出可能的结束实验时剩余的粒子类型数量。

11 5
2 4 2 3 4 4 3 1 4 4 4
1 4
2 8
6 9
8 10
8 11

1
4
1
1
1

提示

【样例解释】

在第一个实验中，我们可以使类型为 $3$ 和 $4$ 的粒子相撞，留下两个类型为 $2$ 的粒子。无法最终得到任何其他类型的粒子。

在第二个实验中，有可能最终剩下每种类型的一些粒子。

在第四和第五个实验中，不论选择哪种碰撞方式，最终都会剩下一些类型为 $4$ 的粒子。

【数据范围】

在所有子任务中，$2 \leq N \leq 5\times 10^5$ 且 $1 \leq Q \leq 5\times 10^5$。

• 子任务 1（13 分）：对于每个 $i = 1, \dots, N，v_i \leq 10$。
• 子任务 2（19 分）：每种类型的粒子最多只有两个。
• 子任务 3（17 分）：$N, Q \leq 2\times 10^3$。
• 子任务 4（19 分）：$N, Q \leq 1\times 10^5$。
• 子任务 5（32 分）：没有额外的约束条件。