数直線上に $1, 2, \ldots, N$ の番号がついた $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} $$

1 行目には、家の数を表す整数 $N$ が与えられる（$2 \le N \le 2 \times 10^5$）。

2 行目には、家の座標を表す $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}$ であることが保証されている。

3 行目には、クエリの数を表す整数 $Q$ が与えられる（$1 \le Q \le 2 \times 10^5$）。

続く $Q$ 行のそれぞれには、2 つの整数 $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