Det finns $N$ hus numrerade $1, 2, \ldots, N$ på en tallinje. Hus $i$ ligger på koordinaten $X_i$. Det garanteras att $X_i < X_{i+1}$ för varje $i$ ($1 \le i \le N - 1$).

För heltal $a, b$ med $1 \le a < b \le N$ säger vi att de på varandra följande husen $a, a + 1, \ldots, b$ bildar ett symmetriskt husintervall om följande villkor gäller:

• För varje $i = 0, 1, \ldots, b - a$ gäller att $X_a + X_b = X_{a+i} + X_{b-i}$.

Du får $Q$ frågor. Behandla dem i ordning.

• I den $i$-te frågan får du heltalen $l_i, r_i$ ($1 \le l_i < r_i \le N$). Bland alla par av heltal $(s, t)$ som uppfyller $l_i \le s < t \le r_i$ sådana att de på varandra följande husen $s, s + 1, \ldots, t$ bildar ett symmetriskt husintervall, skriv ut den maximalt möjliga bredden $X_t - X_s$ på intervallet.

Indata

Indata består av ett enda testfall i följande format:

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

Den första raden innehåller ett heltal $N$, som representerar antalet hus ($2 \le N \le 2 \times 10^5$).

Den andra raden innehåller $N$ heltal $X_1, X_2, \ldots, X_N$, som representerar husens koordinater ($-10^9 \le X_i \le 10^9$). Det garanteras att $X_i < X_{i+1}$ för varje $i$ ($1 \le i \le N - 1$).

Den tredje raden innehåller ett heltal $Q$, som representerar antalet frågor ($1 \le Q \le 2 \times 10^5$).

Var och en av de följande $Q$ raderna innehåller två heltal $l_i$ och $r_i$, som representerar den vänstra och högra ändpunkten för intervallet som anges i den $i$-te frågan ($1 \le l_i < r_i \le N$).

Utdata

För varje fråga, skriv ut den maximalt möjliga bredden.

Exempel

Indata 1

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

Utdata 1

14
8
6
6
4