Matcom Online Grader

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$.

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.