Zum täglichen Melken stehen die $N$ Kühe von Farmer John ($1 \le N \le 50,000$) immer in derselben Reihenfolge. Eines Tages beschließt Farmer John, mit einigen Kühen Ultimate Frisbee zu spielen. Der Einfachheit halber wählt er einen zusammenhängenden Abschnitt der Melkreihe aus. Damit alle Kühe Spaß haben, sollten sie sich allerdings nicht zu stark in ihrer Körperhöhe unterscheiden.

Farmer John hat eine Liste von $Q$ ($1 \le Q \le 200,000$) möglichen Kuhgruppen und ihren Körperhöhen ($1 \le height \le 1,000,000$) erstellt. Hilf ihm, für jede Gruppe den Höhenunterschied zwischen der kleinsten und der größten Kuh zu bestimmen.

Eingabe

Lies die Eingabe von der Standardeingabe.

Zeile 1: zwei durch ein Leerzeichen getrennte ganze Zahlen $N$ und $Q$.

Zeilen $2 \ldots N+1$: Zeile $i+1$ enthält eine ganze Zahl, die Körperhöhe von Kuh $i$.

Zeilen $N+2 \ldots N+Q+1$: zwei ganze Zahlen $A$ und $B$ ($1 \le A \le B \le N$), die den Abschnitt von Kuh $A$ bis Kuh $B$ einschließlich beider Endpunkte angeben.

Ausgabe

Schreibe die Ausgabe auf die Standardausgabe.

Zeilen $1 \ldots Q$: Jede Zeile enthält eine ganze Zahl als Antwort auf die entsprechende Anfrage, den Höhenunterschied zwischen der größten und der kleinsten Kuh im Abschnitt.

Beispiele

Eingabe 1

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

Ausgabe 1

6
3
0

Aufgabenquelle: USACO, Januar 2007, Gold