Frequent Difficulties

In this contest there are \(n\) problems, each with a difficulty value \(a_i\). The difficulties have been pre-sorted in non-decreasing order by the legendary wangxz. Bird Ge does not care about the absolute values of difficulties, he only wants to know, for some interval of problems \(a_l, a_{l+1}, \ldots, a_r\), how many times the most frequent difficulty appears.

Your task is: For each query \((l, r)\), determine the number of occurrences of the most frequent value among the problems \(a_l, a_{l+1}, \ldots, a_r\) (there are \(q\) queries in total).

If you help Bird Ge successfully, he will take you through the provincial selection!

inputFormat

The first line contains two integers \(n\) and \(q\) separated by a space, where \(n\) is the number of problems and \(q\) the number of queries.

The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) in non-decreasing order.

Each of the next \(q\) lines contains two integers \(l\) and \(r\) representing a query (1-indexed).

outputFormat

For each query, output a single integer representing the maximum frequency of any difficulty value in the subarray \(a_l, a_{l+1}, \ldots, a_r\).

sample

10 3
1 2 2 3 3 3 4 4 4 4
1 10
2 5
7 10

4
2
4