Có $N$ ngôi nhà được đánh số $1, 2, \ldots, N$ trên một trục số. Ngôi nhà $i$ nằm tại tọa độ $X_i$. Dữ liệu đảm bảo rằng $X_i < X_{i+1}$ với mọi $i$ ($1 \le i \le N - 1$).

Với các số nguyên $a, b$ thỏa mãn $1 \le a < b \le N$, ta nói các ngôi nhà liên tiếp $a, a + 1, \ldots, b$ tạo thành một đoạn nhà đối xứng nếu điều kiện sau được thỏa mãn:

• Với mọi $i = 0, 1, \ldots, b - a$, đẳng thức $X_a + X_b = X_{a+i} + X_{b-i}$ luôn đúng.

Bạn được cho $Q$ truy vấn. Hãy xử lý chúng theo thứ tự.

• Trong truy vấn thứ $i$, bạn được cho các số nguyên $l_i, r_i$ ($1 \le l_i < r_i \le N$). Trong tất cả các cặp số nguyên $(s, t)$ thỏa mãn $l_i \le s < t \le r_i$ sao cho các ngôi nhà liên tiếp $s, s + 1, \ldots, t$ tạo thành một đoạn nhà đối xứng, hãy in ra độ rộng lớn nhất có thể $X_t - X_s$ của đoạn đó.

Dữ liệu vào

Dữ liệu vào bao gồm một bộ kiểm tra duy nhất có định dạng như sau:

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

Dòng đầu tiên chứa một số nguyên $N$, biểu thị số lượng ngôi nhà ($2 \le N \le 2 \times 10^5$).

Dòng thứ hai chứa $N$ số nguyên $X_1, X_2, \ldots, X_N$, biểu thị tọa độ của các ngôi nhà ($-10^9 \le X_i \le 10^9$). Dữ liệu đảm bảo rằng $X_i < X_{i+1}$ với mọi $i$ ($1 \le i \le N - 1$).

Dòng thứ ba chứa một số nguyên $Q$, biểu thị số lượng truy vấn ($1 \le Q \le 2 \times 10^5$).

Mỗi dòng trong $Q$ dòng tiếp theo chứa hai số nguyên $l_i$ và $r_i$, biểu thị đầu mút bên trái và bên phải của phạm vi được chỉ định trong truy vấn thứ $i$ ($1 \le l_i < r_i \le N$).

Dữ liệu ra

Với mỗi truy vấn, hãy in ra độ rộng lớn nhất có thể.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

14
8
6
6
4