【题目描述】

给定 $n$ 个正整数，其中第 $i$ 个元素记为 $a_i$。

接下来进行 $m$ 次询问。

每次询问给定一个区间 $[l_i,r_i]$，你需要判断这个区间中有多少种众数。

在一个区间中，若某个数的出现次数等于该区间内所有数的最大出现次数，则这个数称为该区间的众数。

一个区间可能有多种众数。

【输入描述】

第一行输入两个整数 $n,m$，表示元素个数和询问次数。

第二行输入 $n$ 个正整数 $a_1,a_2,\ldots,a_n$。

接下来 $m$ 行，第 $i$ 行输入两个整数 $l_i,r_i$，表示一次区间询问。

保证：

• $1\le n,m\le 3000$；
• $1\le a_i\le 10^7$；
• $1\le l_i\le r_i\le n$。

【输出描述】

对于每次询问，输出一行一个整数，表示区间 $[l_i,r_i]$ 中众数的种类数。

【样例 1】

【样例 1 输入】

8 5
1 2 2 3 3 3 2 4
1 3
1 5
4 8
7 8
1 8

【样例 1 输出】

1
2
1
2
2

【样例 1 解释】

第 $2$ 次询问的区间为 $[1,5]$，其中 $2$ 和 $3$ 都出现 $2$ 次，都是众数，因此答案为 $2$。

第 $5$ 次询问的整个序列中，$2$ 和 $3$ 都出现 $3$ 次，因此答案也为 $2$。

【样例 2】

【样例 2 输入】

15 8
4 4 5 6 5 6 7 8 7 8 9 9 9 10 11
1 15
2 10
3 6
7 15
12 15
13 15
1 2
5 14

【样例 2 输出】

1
4
2
1
1
3
1
1

【数据规模与约定】