题目描述

给定一个非递减排列的整数序列 $a_1, a_2, \dots, a_n$，以及若干查询。每个查询给出区间 $[i, j]$（$1 \leq i \leq j \leq n$），请确定该区间内 $a_i$ 到 $a_j$ 中出现次数最多的数值的出现次数。

输入格式

• 输入包含多组测试用例。每组测试用例首行是两个整数 $n$ 和 $q$（$1 \leq n, q \leq 10^5$）。
• 第二行给出 $n$ 个整数 $a_1, \dots, a_n$（$-10^5 \leq a_i \leq 10^5$），满足 $a_1 \leq a_2 \leq \dots \leq a_n$。
• 接下来 $q$ 行，每行包含两个整数 $i$ 和 $j$，表示查询的区间端点。
• 最后以单独的一行 $0$ 结束输入。

输出格式

对每个查询，输出一行整数，表示对应区间内出现次数最多的数值的出现次数。

输入样例

10 3  
-1 -1 1 1 1 1 3 10 10 10  
2 3  
1 10  
5 10  
0  

输出样例

1  
4  
3  

题目来源

乌尔姆本地竞赛（Ulm Local）2007