Triple Jump

Time limit2sMemory limit512 MB

Summary

For each range [L, R], find the maximum A[a]+A[b]+A[c] over indices a<b<c inside the range where b-a <= c-b.

Level: Hard8 of 10
Topics: Divide and conquer, Segment tree, Dynamic programming
Solved: No attempts yet

Problem

There is a very long straight road with $N$ sections numbered from $1$ to $N$ . Section $i$ ( $1 \le i \le N$ ) has firmness $A_i$ .

JOI-kun, the gifted sport star, is going to play triple jump. A triple jump consists of three consecutive jumps. Let $a$ , $b$ , $c$ be the sections where JOI-kun takes off. The following conditions must hold.

$a < b < c$ . The section numbers are increasing.
$b - a \le c - b$ . The first jump is no longer than the second jump.

JOI-kun will perform $Q$ triple jumps. In the $j$ -th triple jump, he takes off from sections in the range $L_j$ to $R_j$ . That is, $L_j \le a < b < c \le R_j$ must hold.

JOI-kun wants to take off from firmer sections. For each triple jump, find the maximum sum of firmness of the sections at which he takes off.

Input

The input is given in the following format. All values in the input are integers.

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

Output

Print $Q$ lines. The $j$ -th line contains the maximum sum of firmness of the sections at which JOI-kun takes off in the $j$ -th triple jump.

Constraints

$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$ )

Examples3

Example 1
Input
```
5
5 2 1 5 3
3
1 4
2 5
1 5
```
Expected output
```
12
9
12
```
Example 2
Input
```
5
5 4 4 5 4
1
1 5
```
Expected output
```
14
```

Example 3

Input

15
12 96 100 61 54 66 37 34 58 21 21 1 13 50 81
12
1 15
3 12
11 14
1 13
5 9
4 6
6 14
2 5
4 15
1 7
1 10
8 13

Expected output