수직선 위에 $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} $$

첫 번째 줄에는 집의 수를 나타내는 정수 $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