數軸上面有 $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