Dada una secuencia $A_1, A_2, \ldots, A_N$ de longitud $N$, donde cada número está entre $1$ y $K$ inclusive. Debes procesar las siguientes consultas:

• l r: imprime $\max\{|x - y| : l \le x, y \le r \text{ y } A_x = A_y\}$.

Entrada

La primera línea contiene dos enteros $N$ y $K$, que representan la longitud de la secuencia y el rango de valores. Aquí $1 \le N \le 100{,}000$, $1 \le K \le 100{,}000$.

La segunda línea contiene $N$ enteros $A_1, A_2, \ldots, A_N$, que satisfacen $1 \le A_i \le K$.

La tercera línea contiene un entero $M$, que representa la cantidad de consultas, $1 \le M \le 100{,}000$.

Las siguientes $M$ líneas contienen cada una dos enteros $l, r$, que representan una consulta, satisfaciendo $1 \le l \le r \le N$.

Salida

Para cada consulta, imprime la respuesta en una línea separada.

Ejemplos

Entrada 1

7 7
4 5 6 6 5 7 4
5
6 6
5 6
3 5
3 7
1 7

Salida 1

0
0
1
1
6