题目描述
给定一个序列 $a_1,\cdots ,a_n$，每次询问一个区间 $[l,r]$ 内出现最多的数的出现次数。 但今天我们不太关心问题的精确答案，只关心问题的数量级。因此，如果精确答案是 $ans$，你的 回答只要在 $[0.5ans,2ans]$ 内就算你对。
输入格式
第一行两个正整数 $n,q$ 表示序列长度和询问次数。 接下来一行输入 $n$ 个正整数，分别表示 $a_1,a_2,\cdots,a_n$。 接下来 $q$ 行每行两个正整数 $[l,r]$ 表示一个询问区间。
输出格式
样例输入：
10 3
1 1 4 5 1 4 1 9 1 9
1 10
1 5
3 10样例输出：
5
3
3大样例
样例 1 解释
注意样例输出是严格正确的答案，但分别在 $[3,10],[2,6],[2,6]$ 区间内的输出都是正确的。
子任务
对于 $100\%$ 的数据，保证 $1\le n,q\le 10^6$， $1\le a_i\le 10^6$。
对于测试点 $1\sim 3$，保证 $n,q\le 10^3$。
对于测试点 $4\sim 5$，保证 $n\le 10^3$。
对于测试点 $6\sim 7$，保证 $n,q\le 10^5$。
对于测试点 $8\sim 10$，无特殊限制。