数轴上有 $N$ 座房屋，编号为 $1, 2, \ldots, N$。房屋 $i$ 位于坐标 $X_i$ 处。保证对于每个 $i$（$1 \le i \le N - 1$），都有 $X_i < X_{i+1}$。

对于满足 $1 \le a < b \le N$ 的整数 $a, b$，如果满足以下条件，我们称连续的房屋 $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$）。在所有满足 $l_i \le s < t \le r_i$ 且使得连续的房屋 $s, s + 1, \ldots, t$ 构成对称房屋区间的整数对 $(s, 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$）。保证对于每个 $i$（$1 \le i \le N - 1$），都有 $X_i < X_{i+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