Se le da una secuencia de $n$ enteros $a_1, a_2,. . . ,$ un orden no decreciente. Además de eso, usted reciben varias consultas que consisten en índices i y j $(1 \leq i \leq j \leq n)$. Para cada consulta, determine el valor más frecuente entre los enteros $a_i ,. . . a_j$.

La entrada consta de un casos de prueba. Cada caso de prueba comienza con una línea que contiene dos enteros $n$ y $q$ $(1 \leq n, q \leq 100000)$. La siguiente línea contiene $n$ enteros $a_1,. . . , a_n (−100000 ≤ a_i ≤ 100000)$ separados por espacios. Puede suponer que para cada i que pertenece a ${1,. . . , n - 1}$: $a_i \leq a_{i + 1}$. Las siguientes líneas $q$ contienen una consulta cada una, que consta de dos enteros i y j $(1 \leq i \leq j \leq n)$, que indican los índices de límite para la consulta.

Para cada consulta, imprima una línea con un entero: el número de ocurrencias del valor más frecuente dentro del rango dado.