트리플 점프

길이가 아주 긴 일직선 도로가 있다. 도로는 1번부터 $N$번까지 번호가 매겨진 $N$개의 구간으로 이루어져 있다. 구간 $i$($1 \le i \le N$)의 단단한 정도는 $A_i$이다.

스포츠 재능이 뛰어난 JOI군은 트리플 점프를 할 예정이다. 트리플 점프는 연속된 세 번의 점프로 이루어진다. JOI군이 도약하는 구간의 번호를 각각 $a$, $b$, $c$라고 할 때, 다음 조건을 만족해야 한다.

• $a < b < c$. 구간 번호는 증가해야 한다.
• $b - a \le c - b$. 첫 번째 점프 거리는 두 번째 점프 거리보다 길지 않아야 한다.

JOI군은 트리플 점프를 $Q$번 수행한다. $j$번째 트리플 점프에서는 번호가 $L_j$부터 $R_j$까지인 구간에서 도약해야 한다. 즉 $L_j \le a < b < c \le R_j$를 만족해야 한다.

JOI군은 더 단단한 구간에서 도약하고 싶어 한다. 각 트리플 점프마다 도약하는 구간들의 단단한 정도 합의 최댓값을 구하라.

입력은 다음 형식으로 주어진다. 입력의 모든 값은 정수다.

N
A1 A2 ... AN
Q
L1 R1
L2 R2
...
LQ RQ

$Q$개의 줄을 출력한다. $j$번째 줄에는 $j$번째 트리플 점프에서 JOI군이 도약하는 구간들의 단단한 정도 합의 최댓값을 출력한다.

• $3 \le N \le 500\,000$
• $1 \le A_i \le 100\,000\,000$ ($1 \le i \le N$)
• $1 \le Q \le 500\,000$
• $1 \le L_j < L_j + 2 \le R_j \le N$ ($1 \le j \le Q$)