D - Valores Frecuentes

Languages: C, C++, Java, Pascal, Python, Tiger, JavaScript, Haskell, C#
Time & Memory limits: (details)

Se tiene una secuencia de  $n$ números enteros $a_1, a_2 , ... , a_n$ en orden no decreciente. Además se dan varias consultas sobre esta secuencia que consiste en dos índices  $i$ y  $j$ $(1 \le i \le j \le n)$.  Por cada consulta se debe determinar el valor más frecuente entre los elementos $a_i, ... , a_j$.

Input

La entrada contiene varios casos de prueba, por cada caso de prueba se tiene una línea que contiene dos números, $n$ y $q$ $(1 \le n, q \le 100000)$. $n$ representa la cantidad de elementos de la secuencia y $q$ la cantidad de consultas que se van a realizar.  La segunda línea contiene $n$ enteros separados por un espacio $a_1 , ... , a_n$ $(-100000 \le a_i \le 100000)$, se puede asumir que para todo $i \in \{1, ..., n-1\}$: $ai \le a_{i+1}$. Luego hay $q$ líneas, donde cada una representa una consulta, cada una de estas consultas está representada por dos números, $i$ y $j$ $(1 \le i \le j \le n)$, separados por un espacio, que representan los extremos de la consulta. El último caso de prueba es representado por un 0.

Output

Por cada consulta se debe de imprimir un entero que representa la cantidad de ocurrencias del valor más frecuente en el rango dado.

Sample test(s)

Input
10 3 -1 -1 1 1 1 1 3 10 10 10 2 3 1 10 5 10 0
Output
1 4 3

Hints

Hint
Tenga en cuenta que la entrada para este problema es enorme.