There are $N$ houses numbered $1, 2, \ldots, N$ on a number line. House $i$ is located at coordinate $X_i$. It is guaranteed that $X_i < X_{i+1}$ for every $i$ ($1 \le i \le N - 1$).

For integers $a, b$ with $1 \le a < b \le N$, we say that the consecutive houses $a, a + 1, \ldots, b$ form a symmetric interval of houses if the following condition holds:

• For every $i = 0, 1, \ldots, b - a$, $X_a + X_b = X_{a+i} + X_{b-i}$ holds.

You are given $Q$ queries. Process them in order.

• In the $i$-th query, you are given integers $l_i, r_i$ ($1 \le l_i < r_i \le N$). Among all pairs of integers $(s, t)$ satisfying $l_i \le s < t \le r_i$ such that the consecutive houses $s, s + 1, \ldots, t$ form a symmetric interval of houses, output the maximum possible width $X_t - X_s$ of the interval.

Input

The input consists of a single test case of the following format:

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

The first line contains an integer $N$, representing the number of houses ($2 \le N \le 2 \times 10^5$).

The second line contains $N$ integers $X_1, X_2, \ldots, X_N$, representing the coordinates of the houses ($-10^9 \le X_i \le 10^9$). It is guaranteed that $X_i < X_{i+1}$ for every $i$ ($1 \le i \le N - 1$).

The third line contains an integer $Q$, representing the number of queries ($1 \le Q \le 2 \times 10^5$).

Each of the following $Q$ lines contains two integers $l_i$ and $r_i$, representing the left and right endpoints of the range specified in the $i$-th query ($1 \le l_i < r_i \le N$).

Output

For each query, output the maximum possible width.

Example

Input 1

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

Output 1

14
8
6
6
4