Para el ordeño diario, las $N$ vacas de Farmer John ($1 \le N \le 50,000$) siempre se colocan en el mismo orden. Un día, Farmer John decide organizar un partido de ultimate con algunas vacas. Para simplificar, elegirá un intervalo contiguo de vacas de la fila de ordeño. Sin embargo, para que todas se diviertan, sus alturas no deben diferir demasiado.

Farmer John ha preparado una lista de $Q$ ($1 \le Q \le 200,000$) posibles grupos de vacas y sus alturas ($1 \le height \le 1,000,000$). Para cada grupo, ayúdale a determinar la diferencia de altura entre la vaca más alta y la más baja.

Entrada

Lee la entrada desde la entrada estándar.

Línea 1: dos enteros $N$ y $Q$ separados por un espacio.

Líneas $2 \ldots N+1$: la línea $i+1$ contiene un entero que es la altura de la vaca $i$.

Líneas $N+2 \ldots N+Q+1$: dos enteros $A$ y $B$ ($1 \le A \le B \le N$), que representan el intervalo de vacas desde $A$ hasta $B$, ambos incluidos.

Salida

Escribe la salida en la salida estándar.

Líneas $1 \ldots Q$: cada línea contiene un entero que responde a la consulta correspondiente e indica la diferencia de altura entre la vaca más alta y la más baja del intervalo.

Ejemplos

Entrada 1

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

Salida 1

6
3
0

Fuente del problema: USACO, enero de 2007, Gold