Per la mungitura quotidiana, le $N$ mucche di Farmer John ($1 \le N \le 50,000$) si mettono sempre in fila nello stesso ordine. Un giorno, Farmer John decide di organizzare una partita di ultimate con alcune mucche. Per semplicità, sceglierà un intervallo contiguo di mucche dalla fila della mungitura. Tuttavia, affinché tutte si divertano, le loro altezze non devono differire troppo.

Farmer John ha preparato un elenco di $Q$ ($1 \le Q \le 200,000$) possibili gruppi di mucche e delle loro altezze ($1 \le height \le 1,000,000$). Per ogni gruppo, aiutatelo a determinare la differenza di altezza tra la mucca più alta e quella più bassa.

Input

Leggete i dati dall’ingresso standard.

Riga 1: due interi $N$ e $Q$ separati da uno spazio.

Righe $2 \ldots N+1$: la riga $i+1$ contiene un intero, l’altezza della mucca $i$.

Righe $N+2 \ldots N+Q+1$: due interi $A$ e $B$ ($1 \le A \le B \le N$), che rappresentano l’intervallo di mucche da $A$ a $B$, estremi inclusi.

Output

Scrivete il risultato sull’uscita standard.

Righe $1 \ldots Q$: ogni riga contiene un intero che risponde alla richiesta corrispondente e indica la differenza di altezza tra la mucca più alta e quella più bassa dell’intervallo.

Esempi

Input 1

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

Output 1

6
3
0

Fonte del problema: USACO, gennaio 2007, Gold