Na osi liczbowej znajduje się $N$ domów ponumerowanych $1, 2, \ldots, N$. Dom $i$ znajduje się we współrzędnej $X_i$. Gwarantowane jest, że $X_i < X_{i+1}$ dla każdego $i$ ($1 \le i \le N - 1$).

Dla liczb całkowitych $a, b$ spełniających $1 \le a < b \le N$ mówimy, że kolejne domy $a, a + 1, \ldots, b$ tworzą symetryczny przedział domów, jeśli spełniony jest następujący warunek:

• Dla każdego $i = 0, 1, \ldots, b - a$ zachodzi równość $X_a + X_b = X_{a+i} + X_{b-i}$.

Danych jest $Q$ zapytań. Przetwórz je po kolei.

• W $i$-tym zapytaniu dane są liczby całkowite $l_i, r_i$ ($1 \le l_i < r_i \le N$). Spośród wszystkich par liczb całkowitych $(s, t)$ spełniających $l_i \le s < t \le r_i$, takich że kolejne domy $s, s + 1, \ldots, t$ tworzą symetryczny przedział domów, wypisz maksymalną możliwą szerokość przedziału $X_t - X_s$.

Wejście

Wejście składa się z pojedynczego przypadku testowego w następującym formacie:

$$ \begin{aligned} &N \\ &X_1 \ X_2 \ \ldots \ X_N \\ &Q \\ &l_1 \ r_1 \\ &l_2 \ r_2 \\ &\vdots \\ &l_Q \ r_Q \end{aligned} $$

Pierwszy wiersz zawiera liczbę całkowitą $N$, oznaczającą liczbę domów ($2 \le N \le 2 \times 10^5$).

Drugi wiersz zawiera $N$ liczb całkowitych $X_1, X_2, \ldots, X_N$, oznaczających współrzędne domów ($-10^9 \le X_i \le 10^9$). Gwarantowane jest, że $X_i < X_{i+1}$ dla każdego $i$ ($1 \le i \le N - 1$).

Trzeci wiersz zawiera liczbę całkowitą $Q$, oznaczającą liczbę zapytań ($1 \le Q \le 2 \times 10^5$).

Każdy z kolejnych $Q$ wierszy zawiera dwie liczby całkowite $l_i$ oraz $r_i$, oznaczające lewy i prawy koniec zakresu określonego w $i$-tym zapytaniu ($1 \le l_i < r_i \le N$).

Wyjście

Dla każdego zapytania wypisz maksymalną możliwą szerokość.

Przykład

Wejście 1

7
-5 -2 0 4 6 9 12
5
1 7
2 6
3 7
4 7
3 6

Wyjście 1

14
8
6
6
4