Hay $N$ casas numeradas $1, 2, \ldots, N$ en una recta numérica. La casa $i$ está ubicada en la coordenada $X_i$. Se garantiza que $X_i < X_{i+1}$ para todo $i$ ($1 \le i \le N - 1$).

Para enteros $a, b$ con $1 \le a < b \le N$, decimos que las casas consecutivas $a, a + 1, \ldots, b$ forman un intervalo simétrico de casas si se cumple la siguiente condición:

• Para todo $i = 0, 1, \ldots, b - a$, se cumple que $X_a + X_b = X_{a+i} + X_{b-i}$.

Se te dan $Q$ consultas. Procésalas en orden.

• En la $i$-ésima consulta, se te dan los enteros $l_i, r_i$ ($1 \le l_i < r_i \le N$). Entre todos los pares de enteros $(s, t)$ que satisfacen $l_i \le s < t \le r_i$ tales que las casas consecutivas $s, s + 1, \ldots, t$ forman un intervalo simétrico de casas, imprime el ancho máximo posible $X_t - X_s$ del intervalo.

Entrada

La entrada consta de un único caso de prueba con el siguiente 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 primera línea contiene un entero $N$, que representa el número de casas ($2 \le N \le 2 \times 10^5$).

La segunda línea contiene $N$ enteros $X_1, X_2, \ldots, X_N$, que representan las coordenadas de las casas ($-10^9 \le X_i \le 10^9$). Se garantiza que $X_i < X_{i+1}$ para todo $i$ ($1 \le i \le N - 1$).

La tercera línea contiene un entero $Q$, que representa el número de consultas ($1 \le Q \le 2 \times 10^5$).

Cada una de las siguientes $Q$ líneas contiene dos enteros $l_i$ y $r_i$, que representan los extremos izquierdo y derecho del rango especificado en la $i$-ésima consulta ($1 \le l_i < r_i \le N$).

Salida

Para cada consulta, imprime el ancho máximo posible.

Ejemplos

Entrada 1

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

Salida 1

14
8
6
6
4