Problem Description

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 Format

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

N
X_1 X_2 ... X_N
Q
l_1 r_1
l_2 r_2
...
l_Q r_Q

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 Format

For each query, output the maximum possible width.

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

14
8
6
6
4