$N$ vacas de Farmer John ($1 \le N \le 50,000$) alinham igual todo dia para ordenha. Um dia organiza ultimate frisbee com algumas. Para simplificar pega intervalo contíguo, mas alturas não devem diferir muito para todas se divertirem.

Lista de $Q$ ($1 \le Q \le 200,000$) grupos possíveis e alturas ($1 \le height \le 1,000,000$): ache diferença maior-menor de cada grupo.

Entrada

Leia da entrada padrão.

Linha 1: inteiros $N$, $Q$ com espaços.

Linhas $2..N+1$: linha $i+1$, altura inteira da vaca $i$.

Linhas $N+2$..$N+Q+1$: inteiros $A$, $B$ ($1 \le A \le B \le N$), intervalo $A$ a $B$ inclusivo.

Saída

Escreva na saída padrão.

Linhas $1..Q$: inteiro por resposta, diferença entre maior e menor altura no intervalo.

Exemplos

Entrada 1

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

Saída 1

6
3
0

Fonte: USACO janeiro 2007, prata