单点时限: 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$ 行,每行一个答案。
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。