Podczas codziennego dojenia $N$ krów Farmer John ($1 \le N \le 50,000$) zawsze ustawia się w tej samej kolejności. Pewnego dnia Farmer John postanawia zorganizować grę w ultimate z niektórymi krowami. Dla uproszczenia wybierze spójny przedział krów z kolejki do dojenia. Aby jednak wszystkie krowy dobrze się bawiły, ich wzrost nie powinien zbytnio się różnić.

Farmer John przygotował listę $Q$ ($1 \le Q \le 200,000$) możliwych grup krów i ich wzrostu ($1 \le height \le 1,000,000$). Dla każdej grupy pomóż mu ustalić różnicę wzrostu między najwyższą a najniższą krową.

Wejście

Wczytaj dane ze standardowego wejścia.

Wiersz 1: dwie liczby całkowite $N$ i $Q$, rozdzielone spacją.

Wiersze $2 \ldots N+1$: wiersz $i+1$ zawiera jedną liczbę całkowitą — wzrost krowy $i$.

Wiersze $N+2 \ldots N+Q+1$: dwie liczby całkowite $A$ i $B$ ($1 \le A \le B \le N$), określające przedział krów od $A$ do $B$ włącznie.

Wyjście

Wypisz wynik na standardowe wyjście.

Wiersze $1 \ldots Q$: każdy wiersz zawiera jedną liczbę całkowitą będącą odpowiedzią na odpowiednie zapytanie i oznaczającą różnicę wzrostu między najwyższą a najniższą krową w przedziale.

Przykład

Wejście 1

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

Wyjście 1

6
3
0

Źródło zadania: USACO, styczeń 2007, Gold