Il y a $N$ maisons numérotées $1, 2, \ldots, N$ sur une droite graduée. La maison $i$ est située à la coordonnée $X_i$. Il est garanti que $X_i < X_{i+1}$ pour tout $i$ ($1 \le i \le N - 1$).

Pour des entiers $a, b$ tels que $1 \le a < b \le N$, on dit que les maisons consécutives $a, a + 1, \ldots, b$ forment un intervalle symétrique de maisons si la condition suivante est vérifiée :

• Pour tout $i = 0, 1, \ldots, b - a$, l'égalité $X_a + X_b = X_{a+i} + X_{b-i}$ est vérifiée.

On vous donne $Q$ requêtes. Traitez-les dans l'ordre.

• Dans la $i$-ème requête, on vous donne deux entiers $l_i, r_i$ ($1 \le l_i < r_i \le N$). Parmi tous les couples d'entiers $(s, t)$ vérifiant $l_i \le s < t \le r_i$ tels que les maisons consécutives $s, s + 1, \ldots, t$ forment un intervalle symétrique de maisons, affichez la largeur maximale possible $X_t - X_s$ de l'intervalle.

Entrée

L'entrée consiste en un seul cas de test au format suivant :

$$ \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 première ligne contient un entier $N$, représentant le nombre de maisons ($2 \le N \le 2 \times 10^5$).

La deuxième ligne contient $N$ entiers $X_1, X_2, \ldots, X_N$, représentant les coordonnées des maisons ($-10^9 \le X_i \le 10^9$). Il est garanti que $X_i < X_{i+1}$ pour tout $i$ ($1 \le i \le N - 1$).

La troisième ligne contient un entier $Q$, représentant le nombre de requêtes ($1 \le Q \le 2 \times 10^5$).

Chacune des $Q$ lignes suivantes contient deux entiers $l_i$ et $r_i$, représentant les extrémités gauche et droite de la plage spécifiée dans la $i$-ème requête ($1 \le l_i < r_i \le N$).

Sortie

Pour chaque requête, affichez la largeur maximale possible.

Exemples

Entrée 1

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

Sortie 1

14
8
6
6
4