题目描述

给定一个大小为 $n$ 的非降序列 $a_i$ ，并给定 $q$ 组询问，每次询问给出 $i, j$ ，询问区间 $[i, j]$ 中连续出现次数最多的数出现的次数。

输入

第一行两个正整数 $n, q$，表示序列的长度和询问的次数。

输出

对于每一次询问，输出一个正整数表示区间内出现最多的数出现的次数。

样例

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

1
4
3

数据范围

对于 $30\%$ 的数据：$1 \le n, q \le 100, 1 \le a_i \le 50$。

对于 $100\%$ 的数据：$1 \le n, q \le 10^5, 1 \le a_i \le 10^5, 1 \le i \le j \le n$。