Ci sono $N$ case numerate $1, 2, \ldots, N$ su una retta numerica. La casa $i$ si trova alla coordinata $X_i$. È garantito che $X_i < X_{i+1}$ per ogni $i$ ($1 \le i \le N - 1$).

Per gli interi $a, b$ con $1 \le a < b \le N$, diciamo che le case consecutive $a, a + 1, \ldots, b$ formano un intervallo simmetrico di case se vale la seguente condizione:

• Per ogni $i = 0, 1, \ldots, b - a$, vale $X_a + X_b = X_{a+i} + X_{b-i}$.

Ti vengono date $Q$ query. Elaborale in ordine.

• Nella $i$-esima query, ti vengono dati gli interi $l_i, r_i$ ($1 \le l_i < r_i \le N$). Tra tutte le coppie di interi $(s, t)$ che soddisfano $l_i \le s < t \le r_i$ tali che le case consecutive $s, s + 1, \ldots, t$ formino un intervallo simmetrico di case, stampa la massima ampiezza possibile $X_t - X_s$ dell'intervallo.

Input

L'input è costituito da un singolo caso di test nel seguente formato:

$$ \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} $$

La prima riga contiene un intero $N$, che rappresenta il numero di case ($2 \le N \le 2 \times 10^5$).

La seconda riga contiene $N$ interi $X_1, X_2, \ldots, X_N$, che rappresentano le coordinate delle case ($-10^9 \le X_i \le 10^9$). È garantito che $X_i < X_{i+1}$ per ogni $i$ ($1 \le i \le N - 1$).

La terza riga contiene un intero $Q$, che rappresenta il numero di query ($1 \le Q \le 2 \times 10^5$).

Ciascuna delle seguenti $Q$ righe contiene due interi $l_i$ e $r_i$, che rappresentano gli estremi sinistro e destro dell'intervallo specificato nella $i$-esima query ($1 \le l_i < r_i \le N$).

Output

Per ogni query, stampa la massima ampiezza possibile.

Esempio

Input 1

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

Output 1

14
8
6
6
4