Lukusuoralla on $N$ taloa, jotka on numeroitu $1, 2, \ldots, N$. Talo $i$ sijaitsee koordinaatissa $X_i$. On taattu, että $X_i < X_{i+1}$ jokaisella $i$ ($1 \le i \le N - 1$).

Kokonaisluvuille $a, b$, joille $1 \le a < b \le N$, sanomme, että peräkkäiset talot $a, a + 1, \ldots, b$ muodostavat symmetrisen talovälin, jos seuraava ehto pätee:

• Jokaisella $i = 0, 1, \ldots, b - a$ pätee $X_a + X_b = X_{a+i} + X_{b-i}$.

Sinulle annetaan $Q$ kyselyä. Käsittele ne järjestyksessä.

• $i$-nnessä kyselyssä sinulle annetaan kokonaisluvut $l_i, r_i$ ($1 \le l_i < r_i \le N$). Kaikkien sellaisten kokonaislukuparien $(s, t)$ joukosta, jotka toteuttavat ehdon $l_i \le s < t \le r_i$ ja joilla peräkkäiset talot $s, s + 1, \ldots, t$ muodostavat symmetrisen talovälin, tulosta välin suurin mahdollinen leveys $X_t - X_s$.

Syöte

Syöte koostuu yhdestä testitapauksesta seuraavassa muodossa:

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

Ensimmäinen rivi sisältää kokonaisluvun $N$, joka kuvaa talojen lukumäärää ($2 \le N \le 2 \times 10^5$).

Toinen rivi sisältää $N$ kokonaislukua $X_1, X_2, \ldots, X_N$, jotka kuvaavat talojen koordinaatteja ($-10^9 \le X_i \le 10^9$). On taattu, että $X_i < X_{i+1}$ jokaisella $i$ ($1 \le i \le N - 1$).

Kolmas rivi sisältää kokonaisluvun $Q$, joka kuvaa kyselyiden lukumäärää ($1 \le Q \le 2 \times 10^5$).

Jokainen seuraavista $Q$ rivistä sisältää kaksi kokonaislukua $l_i$ ja $r_i$, jotka kuvaavat $i$-nnessä kyselyssä määritellyn alueen vasenta ja oikeaa päätepistettä ($1 \le l_i < r_i \le N$).

Tuloste

Tulosta jokaiseen kyselyyn suurin mahdollinen leveys.

Esimerkki

Syöte 1

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

Tuloste 1

14
8
6
6
4