Pour la traite quotidienne, les $N$ vaches de Farmer John ($1 \le N \le 50,000$) se rangent toujours dans le même ordre. Un jour, Farmer John décide d’organiser une partie d’ultimate avec certaines vaches. Pour simplifier les choses, il choisira un intervalle contigu de vaches dans la file de la traite. Toutefois, pour que toutes s’amusent, leurs tailles ne doivent pas trop différer.

Farmer John a dressé une liste de $Q$ ($1 \le Q \le 200,000$) groupes possibles de vaches et de leurs tailles ($1 \le height \le 1,000,000$). Pour chaque groupe, aidez-le à déterminer la différence de taille entre la plus grande et la plus petite vache.

Entrée

Lisez les données sur l’entrée standard.

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

Lignes $2 \ldots N+1$ : la ligne $i+1$ contient un entier donnant la taille de la vache $i$.

Lignes $N+2 \ldots N+Q+1$ : deux entiers $A$ et $B$ ($1 \le A \le B \le N$), représentant les vaches de $A$ à $B$, bornes incluses.

Sortie

Écrivez le résultat sur la sortie standard.

Lignes $1 \ldots Q$ : chaque ligne contient un entier répondant à la requête correspondante, la différence de taille entre la plus grande et la plus petite vache 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 du problème : USACO, janvier 2007, Gold