题目描述

给定一个长度为 $n$ 的非下降整数序列 $a_1, a_2, \ldots, a_n$ ，以及 $q$ 次询问。每次询问包含两个参数 $L$ 和 $R$ ，要求计算在序列的区间 $[L, R]$（即 $a_L, \ldots, a_R$ ）内，所有出现过的数字中出现次数最多的数字的出现次数，也就是最大频率。

输入格式

1. 第一行输入两个正整数 $n$ 和 $q$ ，分别表示序列长度和询问次数。
2. 第二行输入 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ，代表序列的每一项。
3. 接下来 $q$ 行，每行输入两个正整数 $L_i$ 和 $R_i$ ，表示第 $i$ 次询问的参数。

输出格式

输出共 $q$ 行，第 $i$ 行输出第 $i$ 个询问对应的答案。

数据范围

• 对于 $30\%$ 的数据，$1 \leq n, q \leq 100$ 。
• 对于 $60\%$ 的数据，$1 \leq n, q \leq 10^4$ 。
• 对于 $100\%$ 的数据，$1 \leq n, q \leq 10^5$ ，$-10^9 \leq a_1 \leq a_2 \leq \ldots \leq a_n \leq 10^9$ ，$1 \leq L \leq R \leq n$ 。

输入输出样例

输入样例

10 4
-2 -2 -1 2 3 3 3 7 8 8
1 3
2 4
1 8
7 10

输出样例

2
1
3
2