题目描述

给定一个非递减的整数序列 $a_1, a_2, \dots, a_n$。

此外，还会给出多个查询，每个查询由两个索引 $i$ 和 $j$ 组成（$1 \leq i \leq j \leq n$）。

对于每个查询，确定在范围 $a_i, \dots, a_j$ 内出现次数最多的值的出现次数。

输入格式

第一行包含两个整数 $n$ 和 $q$（$1 \leq n, q \leq 100000$）。

接下来的一行包含 $n$ 个整数 $a_1, \dots, a_n$（$-100000 \leq a_i \leq 100000$，对于每个 $i \in \{1, \dots, n\}$），用空格分隔。

可以保证对于每个 $i \in \{1, \dots, n-1\}$，都有 $a_i \leq a_{i+1}$。

接下来的 $q$ 行每行包含一个查询，由两个整数 $i$ 和 $j$ 组成（$1 \leq i \leq j \leq n$），表示查询的边界索引。

输出格式

对于每个查询，输出一行，包含一个整数：在给定范围内出现次数最多的值的出现次数。

样例

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

1
4
3

样例解释

$[3,6]$之间，全是$1$，出现$4$次。

$[5,10]$之间，出现最多的是数字$10$，出现$3$次。