题目描述

给定一个长度为 n 的整数序列 a1, a2, …, an，且该序列已经按非降序排列（即每一个元素都不大于它后面的元素）。接下来有若干个查询，每个查询给出左右端点 i 和 j（1 ≤ i ≤ j ≤ n）。对于每个查询，在子区间 a[i], a[i+1], …, a[j] 中，找出出现次数最多的那个数，输出该数在本区间中出现的次数。

注意：如果你直接用简单的 O(n) 方法或者把子区间取出再排序、统计，最坏情况下会超时，需要用更快的算法。

输入格式

• 输入由若干测试用例组成，每个测试用例格式如下：

  1. 一行两个整数 n 和 q，表示序列长度和查询次数，满足 1 ≤ n, q ≤ 100000。
  2. 一行 n 个整数 a1, a2, …, an，范围在 –100000 到 100000 之间，并且保证 a1 ≤ a2 ≤ … ≤ an。
  3. 接下来 q 行，每行两个整数 i 和 j，表示查询区间的左右端点（1 ≤ i ≤ j ≤ n）。

• 最后会出现一行单独的“0”，表示所有测试用例结束，无需再处理。

输出格式

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

样例

输入：

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

输出：

1
4
3

样例说明

• 查询区间 [2,3] 即序列 –1, 1，两者都只出现一次，最多次数为 1。
• 查询区间 [1,10] 整段中，数字 1 出现了 4 次，是最多的。
• 查询区间 [5,10] 即序列 1,1,3,10,10,10，数字 10 出现了 3 次，是最多的。