Les $N$ vaches de Farmer John ($1 \le N \le 50,000$) s'alignent chaque jour dans le même ordre pour la traite. Il organise un ultimate frisbee avec certaines. Pour simplifier, il prend un intervalle contigu, mais pour leur plaisir les tailles ne doivent pas trop différer.

Liste de $Q$ ($1 \le Q \le 200,000$) groupes potentiels et tailles ($1 \le height \le 1,000,000$) : trouvez la différence maximale-minimale de chaque groupe.

Entrée

Lisez sur l'entrée standard.

Ligne 1 : entiers $N$, $Q$ séparés par un espace.

Lignes $2..N+1$ : ligne $i+1$, entier taille de vache $i$.

Lignes $N+2$..$N+Q+1$ : entiers $A$, $B$ ($1 \le A \le B \le N$), intervalle $A$ à $B$ inclus.

Sortie

Écrivez sur la sortie standard.

Lignes $1..Q$ : un entier par réponse, différence entre plus grande et plus petite taille de l'intervalle.

Exemples

Entrée 1

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

Sortie 1

6
3
0

Source : USACO janvier 2007, argent