该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

重复标记

题目描述

档案员把 $N$ 张卡片从左到右排成一列，位置依次编号为 $1,2,\ldots,N$。第 $i$ 张卡片上写着一个标记 $c_i$。标记相同的卡片属于同一种类。

档案员要进行 $Q$ 次查询。每次给出两个位置 $l,r$，请统计第 $l$ 张到第 $r$ 张卡片中，至少出现两次的标记有多少种。区间包含两个端点。

同一种标记无论出现两次、三次还是更多次，都只计为一种。只出现一次的标记不计入答案。各次查询相互独立，卡片及其标记始终不变。

输入格式

第一行包含两个整数 $N,Q$，分别表示卡片数量和查询次数。

第二行包含 $N$ 个整数 $c_1,c_2,\ldots,c_N$，依次表示每张卡片上的标记。

接下来 $Q$ 行，每行包含两个整数 $l_i,r_i$，表示第 $i$ 次查询的闭区间。

数据保证：

• $1\le N,Q\le 5\times 10^5$；
• $1\le c_i\le N$；
• $1\le l_i\le r_i\le N$；
• 所有输入均为整数。

输出格式

输出 $Q$ 行。第 $i$ 行输出一个整数，表示第 $i$ 次查询中至少出现两次的标记种数，顺序与输入的查询顺序一致。没有这样的标记时输出 $0$。

输入输出样例

输入 #1

6 4
1 2 1 2 1 3
1 5
2 4
3 6
6 6

输出 #1

2
1
1
0

输入 #2

4 4
4 4 4 4
2 4
1 1
1 4
3 4

输出 #2

1
0
1
1

输入 #3

1 1
1
1 1

输出 #3

0

样例说明

样例 1 中，区间 $[1,5]$ 内标记 $1$ 出现三次，标记 $2$ 出现两次，因此答案是 $2$。区间 $[2,4]$ 内只有标记 $2$ 出现两次；区间 $[3,6]$ 内只有标记 $1$ 出现两次。区间 $[6,6]$ 只包含一张卡片，答案为 $0$。

样例 2 中，只要区间包含至少两张卡片，标记 $4$ 就满足要求，但无论区间多长都只贡献 $1$。