时间限制： 5.0 秒 1.0 秒

空间限制： 512 MB

题目描述

给一个长度为 $n$ 的序列 $a_1,a_2,\cdots,a_n$。现在有 $q$ 次询问，每次询问有两个数，分别为 $l$ 和 $r$，求 $a_l,\cdots,a_r$ 中有多少个不同的数恰好出现了两次。

输入格式

从标准输入读入数据。

第一行输入两个整数 $n,q$。

第二行是用空格分隔的 $n$ 个整数 $a_1,\cdots,a_n$。

接下来 $q$ 行，每行两个整数 $l,r$。

输出格式

输出到标准输出。

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

5 1
1 2 1 1 1
1 3

1

样例 1 解释

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

5 2
1 1 1 1 1
3 5
2 3

0
1

样例 2 解释

由于第 3 个数到第 5 个数都是 1，所以 1 出现了三次，没有任何一个数符合“恰好出现两次”的要求。

5 2
0 0 1 1 2
3 3
1 5

0
2

样例 3 解释

由于在这五个数中出现了两个 0 和两个 1，所以 0 和 1 都是符合要求的。所以输出 2。

子任务

对于 $40\%$ 的数据，保证 $n,q\le 5000$。

对于所有数据，保证：

• $1\le n,q\le 5\times 10^5$
• $0\le a_i \le 10^9$
• $1\le l\le r\le n$