Það eru $N$ hús númeruð $1, 2, \ldots, N$ á talnalínu. Hús $i$ er staðsett í hniti $X_i$. Tryggt er að $X_i < X_{i+1}$ fyrir hvert $i$ ($1 \le i \le N - 1$).

Fyrir heiltölur $a, b$ þannig að $1 \le a < b \le N$ segjum við að samliggjandi húsin $a, a + 1, \ldots, b$ myndi samhverft húsabil ef eftirfarandi skilyrði gildir:

• Fyrir hvert $i = 0, 1, \ldots, b - a$ gildir $X_a + X_b = X_{a+i} + X_{b-i}$.

Þér eru gefnar $Q$ fyrirspurnir. Vinndu úr þeim í röð.

• Í $i$-tu fyrirspurninni eru þér gefnar heiltölurnar $l_i, r_i$ ($1 \le l_i < r_i \le N$). Meðal allra para af heiltölum $(s, t)$ sem uppfylla $l_i \le s < t \le r_i$ þannig að samliggjandi húsin $s, s + 1, \ldots, t$ myndi samhverft húsabil, skrifaðu út mesta mögulega breidd $X_t - X_s$ á bilinu.

Inntak

Inntakið samanstendur af einu prófunartilfelli á eftirfarandi sniði:

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

Fyrsta línan inniheldur heiltölu $N$, sem táknar fjölda húsa ($2 \le N \le 2 \times 10^5$).

Önnur línan inniheldur $N$ heiltölur $X_1, X_2, \ldots, X_N$, sem tákna hnit húsanna ($-10^9 \le X_i \le 10^9$). Tryggt er að $X_i < X_{i+1}$ fyrir hvert $i$ ($1 \le i \le N - 1$).

Þriðja línan inniheldur heiltölu $Q$, sem táknar fjölda fyrirspurna ($1 \le Q \le 2 \times 10^5$).

Hver af næstu $Q$ línum inniheldur tvær heiltölur $l_i$ og $r_i$, sem tákna vinstri og hægri endapunkta sviðsins sem tilgreint er í $i$-tu fyrirspurninni ($1 \le l_i < r_i \le N$).

Úttak

Fyrir hverja fyrirspurn skal skrifa út mestu mögulegu breidd.

Dæmi

Inntak 1

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

Úttak 1

14
8
6
6
4