Ferume me preguntó si podía resolver esto más rápido que $O(n\sqrt{n} \log n)$. ¡Y resultó que sí! Gracias a él por crear este problema y no dejar que viviera con una solución aburrida.

Sea $S$ un multiconjunto que contiene enteros no negativos. Puedes realizar la siguiente operación en $S$ un número arbitrario de veces (posiblemente cero): elige $x$ tal que haya al menos dos ocurrencias de $x$ en $S$, elimina una de las ocurrencias pero inserta una ocurrencia de $(x - 1)$ o $(x + 1)$ en su lugar (solo puedes insertar $(x - 1)$ si es no negativo). Sea $F(S)$ el mex máximo que puedes lograr con estas operaciones. Aquí, $\text{mex}(S)$ es el entero no negativo mínimo que no está presente en $S$.

Se te da un arreglo $a$ de longitud $n$ y $q$ consultas $[l; r]$. Para cada consulta, encuentra $F(\{a_l, a_{l+1}, \dots, a_r\})$.

Entrada

La primera línea contiene dos enteros $n, q$ ($1 \le n, q \le 5 \cdot 10^5$) — el tamaño del arreglo y el número de consultas.

La segunda línea contiene el arreglo de enteros $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 5 \cdot 10^5$).

Las siguientes $q$ líneas contienen dos enteros $l_i, r_i$ ($1 \le l_i \le r_i \le n$) — la $i$-ésima consulta.

Salida

Imprime las respuestas a las consultas en el orden en que aparecen en la entrada, en líneas separadas.

Ejemplos

Entrada 1

3 3
0 0 2
1 3
2 3
3 3

Salida 1

3
1
0

Entrada 2

3 2
1 2 2
1 2
1 3

Salida 2

0
3