Las $N$ vacas de Farmer John ($1 \le N \le 50,000$) se alinean igual diariamente para ordeño. Un día organiza frisbee ultimate con algunas. Para simplificar toma intervalo contiguo, pero alturas no deben diferir mucho para divertirse todas.

Lista de $Q$ ($1 \le Q \le 200,000$) grupos posibles y alturas ($1 \le height \le 1,000,000$): halla diferencia entre mayor y menor de cada uno.

Entrada

Lee de entrada estándar.

Línea 1: enteros $N$, $Q$ separados por espacios.

Líneas $2..N+1$: línea $i+1$, altura entera de vaca $i$.

Líneas $N+2$..$N+Q+1$: enteros $A$, $B$ ($1 \le A \le B \le N$), rango $A$ a $B$ inclusive.

Salida

Escribe en salida estándar.

Líneas $1..Q$: entero por respuesta, diferencia mayor-menor del rango.

Ejemplos

Entrada 1

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

Salida 1

6
3
0

Fuente: USACO enero 2007, plata