[AdditionalFile5510.zip](file://AdditionalFile5510.zip?type=additional_file)

#5510. 「COI 2024」CERN

标签: 传统 | 时间限制: 4000 ms | 内存限制: 512 MiB |

题目描述

译自 COI 2024 T1「CERN」

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

我们考虑一个由 $N$ 个粒子组成的序列。每个粒子都由其类型 $v_{i}$ 定义，该类型由一个 $1$ 到 $N$ 之间的正整数表示。

在最新的研究中，需要进行 $Q$ 次实验。在第 $i$ 次实验中，我们观察序列中从第 $l_{i}$ 个到第 $r_{i}$ $(l_{i}<r_{i})$ 个的所有粒子。在观察到的粒子中，我们可以选择任意两个不同类型的粒子，在加速器中使它们碰撞，这会导致两个粒子都被摧毁。只要观察到的粒子中还存在两种不同类型的粒子，我们就重复这个碰撞过程。实验结束的条件是：要么所有观察到的粒子都被摧毁，要么只剩下一些相同类型的粒子。当然，根据我们碰撞粒子的顺序，实验结束时可能会剩下不同类型的粒子。

由于粒子碰撞的成本不菲，你决定只在理论上进行实验。现在，对于每次实验，你感兴趣的是，存在多少种粒子类型，使得实验有可能以剩下该类型的粒子而告终。

输入格式

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

下一行包含一个由 $N$ 个数组成的序列 $v_{1}, \ldots, v_{N}$，代表粒子们的类型。

接下来的 $Q$ 行中，每一行都有一对正整数 $l_{i}$ 和 $r_{i}$ $(1 \leq l_{i}<r_{i} \leq N)$，代表第 $i$ 次实验中观察粒子的区间。

输出格式

对于 $Q$ 次实验中的每一次，都在新的一行中输出所求的粒子类型数量。

样例

输入

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

数据范围与提示

对于所有输入数据，满足 $2 \leq N \leq 500\,000$ 且 $1 \leq Q \leq 500\,000$。

详细子任务附加限制及分值如下表所示：