题目描述

给定一个长度为 $n$ 的不下降序列 $a_1,a_2,...,a_n$，及 $q$ 次询问，每次询问包含两个参数 $L , R$，请你计算出区间$[L,R]$内，即$a_L,...,a_R$中，所有出现过的数字中的最大频率。

所谓最大频率，指所有数字中，出现次数最多的数字出现的次数。

输入格式

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

输出格式

输出共$q$行，第$i$行输出对于第$i$个问题的答案

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

2
1
3
2

数据范围

• 对于 $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 ...\leq a_n \leq 10^9$，$1 \leq L \leq R \leq n$