На числовій прямій розташовано $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