2017 计算机系暑期夏令营机考

F. 送分题

单点时限: 5.0 sec

内存限制: 512 MB

给一个长度为 $N$ 的序列,$a_1, a_2, \ldots, a_N$。现在有 $Q$ 次询问,每次询问有两个数,分别为 $L$ 和 $R$,求 $a_L, a_{L+1}, \ldots, a_R$ 中有多少个不同的数恰好出现了两次。

输入格式

第一行是两个整数 $N$ 和 $Q$ $(1 \leq N, Q \leq 500~000)$。

第二行是用空格隔开的 $N$ 个整数 $a_1, a_2, \ldots, a_N$ $(0 \leq a_i \leq 10^9)$。

接下来 $Q$ 行,每行两个整数 $L$ 和 $R$ $(1 \leq L \leq R \leq N)$。

对于 $50\%$ 的数据,$N, Q \leq 5~000$。

输出格式

对于 $Q$ 次询问,输出 $Q$ 行,每行一个答案。

样例

Input
5 1
1 2 1 1 1
1 3
Output
1
Input
5 2
1 1 1 1 1
3 5
2 3
Output
0
1
Input
5 2
0 0 1 1 2
3 3
1 5
Output
0
2

提示

第一组样例:由于第 1 个数到第 3 个数中有两个 1 和一个 2,1 恰好出现了两次,所以有一个符合要求的数,输出 1。

第二组样例:由于第 3 个数到第 5 个数都是 1,所以 1 出现了三次,没有任何一个数符合「恰好出现两次」的要求。

第三组样例:由于在这五个数中出现了两个 1 和两个 2,所以 1 和 2 都是符合要求的。所以输出 2。