Para a ordenha diária, as $N$ vacas de Farmer John ($1 \le N \le 50,000$) sempre se alinham na mesma ordem. Um dia, Farmer John decide organizar uma partida de ultimate com algumas vacas. Para simplificar, escolherá um intervalo contíguo de vacas da fila de ordenha. Porém, para todas se divertirem, suas alturas não devem diferir demais.

Farmer John fez uma lista de $Q$ ($1 \le Q \le 200,000$) possíveis grupos de vacas e suas alturas ($1 \le height \le 1,000,000$). Para cada grupo, ajude-o a determinar a diferença de altura entre a vaca mais alta e a mais baixa.

Entrada

Leia a entrada da entrada padrão.

Linha 1: dois inteiros $N$ e $Q$ separados por um espaço.

Linhas $2 \ldots N+1$: a linha $i+1$ contém um inteiro que representa a altura da vaca $i$.

Linhas $N+2 \ldots N+Q+1$: dois inteiros $A$ e $B$ ($1 \le A \le B \le N$), representando o intervalo de vacas de $A$ a $B$, inclusive.

Saída

Escreva a saída na saída padrão.

Linhas $1 \ldots Q$: cada linha contém um inteiro que responde à consulta correspondente e indica a diferença de altura entre a vaca mais alta e a mais baixa do intervalo.

Exemplos

Entrada 1

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

Saída 1

6
3
0

Créditos do problema: USACO, janeiro de 2007, Gold