На числовой прямой расположены $N$ домов, пронумерованных $1, 2, \ldots, N$. Дом $i$ находится в координате $X_i$. Гарантируется, что $X_i < X_{i+1}$ для каждого $i$ ($1 \le i \le N - 1$).

Для целых чисел $a, b$, удовлетворяющих условию $1 \le a < b \le N$, будем говорить, что подряд идущие дома $a, a + 1, \ldots, b$ образуют симметричный отрезок домов, если выполняется следующее условие:

• Для каждого $i = 0, 1, \ldots, b - a$ выполняется равенство $X_a + X_b = X_{a+i} + X_{b-i}$.

Вам даны $Q$ запросов. Обработайте их по порядку.

• В $i$-м запросе вам даны целые числа $l_i, r_i$ ($1 \le l_i < r_i \le N$). Среди всех пар целых чисел $(s, t)$, удовлетворяющих условию $l_i \le s < t \le r_i$, таких, что подряд идущие дома $s, s + 1, \ldots, t$ образуют симметричный отрезок домов, выведите максимально возможную ширину отрезка $X_t - X_s$.

Входные данные

Входные данные состоят из одного набора входных данных в следующем формате:

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

Первая строка содержит целое число $N$, обозначающее количество домов ($2 \le N \le 2 \times 10^5$).

Вторая строка содержит $N$ целых чисел $X_1, X_2, \ldots, X_N$, обозначающих координаты домов ($-10^9 \le X_i \le 10^9$). Гарантируется, что $X_i < X_{i+1}$ для каждого $i$ ($1 \le i \le N - 1$).

Третья строка содержит целое число $Q$, обозначающее количество запросов ($1 \le Q \le 2 \times 10^5$).

Каждая из следующих $Q$ строк содержит два целых числа $l_i$ и $r_i$, обозначающих левую и правую границы диапазона, заданного в $i$-м запросе ($1 \le l_i < r_i \le N$).

Выходные данные

Для каждого запроса выведите максимально возможную ширину.

Примеры

Входные данные 1

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

Выходные данные 1

14
8
6
6
4