$N$ mucche di Farmer John ($1 \le N \le 50,000$) si allineano uguale ogni giorno per mungitura. Un giorno gioca ultimate frisbee con alcune. Per semplicità sceglie tratto contiguo, ma per divertire tutte le altezze non devono variare troppo.

$Q$ ($1 \le Q \le 200,000$) gruppi possibili e altezze ($1 \le height \le 1,000,000$): trova differenza massima-minima per ognuno.

Input

Leggi dall'input standard.

Riga 1: interi $N$, $Q$ con spazi.

Righe $2..N+1$: riga $i+1$, altezza intera della mucca $i$.

Righe $N+2$..$N+Q+1$: interi $A$, $B$ ($1 \le A \le B \le N$), tratto $A$ a $B$ incluso.

Output

Scrivi nell'output standard.

Righe $1..Q$: intero per risposta, differenza tra più alta e più bassa nel tratto.

Esempi

Input 1

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

Output 1

6
3
0

Fonte: USACO gennaio 2007, argento