3307. 送分题

输入格式

第一行是两个整数 $N$ 和 $Q$ $(1\le N,Q\le 500000)$。

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

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

对于 $50\mathrm{\%}$ 的数据，$N,Q\le 5000$。

输出格式

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

5 1
1 2 1 1 1
1 3

1

5 2
1 1 1 1 1
3 5
2 3

0
1

5 2
0 0 1 1 2
3 3
1 5

0
2

提示

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

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

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