There is a very long straight road, which consists of $N$ sections numbered from $1$ through $N$. Each section has specific firmness, and the firmness of the section $i$ $(1\le i\le N)$ is $A_i$.

JOI-kun, the gifted sports star, is going to play triple jump. A triple jump consists of three consecutive jumps. Let $a,b,c$ be the numbers of sections at which JOI-kun takes off, then the following conditions should be met.

• $a<b<c$. Namely, the numbers of the sections should be increasing.
• $b-a\le c-b$. Namely, the jumping distance of the first jump should be less than or equal to the jumping distance of the second jump.

JOI-kun is going to perform $Q$ triple jumps. In the $j$-th $(1\le j\le Q)$ triple jump, he should take off at sections whose numbers are in the range of $L_j$ to $R_j$. In other words, $L_j\le a<b<c\le R_j$ must be held.

JOI-kun wants to take off at firmer sections. For each triple jump, JOI-kun is curious to know the maximum sum of firmness of the sections at which JOI-kun takes off.

Write a program that, given the number of sections and the information of triple jumps, calculates for each triple jump the maximum sum of firmness of the sections at which JOI-kun takes off.

Input Specification

Read the following data from the standard input. All the values in the input are integers.

$N$

$A_1{A}_2\dots A_N$

$Q$

$L_1{R}_1$

$L_2{R}_2$

$⋮$

$L_Q{R}_Q$

Output Specification

Write $Q$ lines to the standard output. The $j$-th $(1\le j\le Q)$ line should contain 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 500000$.
• $1\le A_i\le 100000000$ $(1\le i\le N)$.
• $1\le Q\le 500000$.
• $1\le L_j<L_j+2\le R_j\le N$ $(1\le j\le Q)$.

Subtasks

1. (5 points) $N\le 100$, $Q\le 100$.
2. (14 points) $N\le 5000$.
3. (27 points) $N\le 200000$, $Q=1$, $L_1=1$, $R_1=N$.
4. (54 points) No additional constraints.

Sample Input 1

5
5 2 1 5 3
3
1 4
2 5
1 5

Sample Output 1

12
9
12

Explanation for Sample 1

In the first jump, JOI-kun can achieve the maximum sum of $12$ by taking off at the sections $1$, $2$ and $4$.

In the second jump, JOI-kun can achieve the maximum sum of $9$ by taking off at the sections $3$, $4$ and $5$. If he takes off at the sections $2$, $4$ and $5$, the sum of firmness is $10$, but $b-a\le c-b$ is not satisfied.

In the third jump, JOI-kun can achieve the maximum sum of $12$ by taking off at the sections $1$, $2$ and $4$. If he takes off at the sections $1$, $4$ and $5$, the sum of firmness is $13$, but $b-a\le c-b$ is not satisfied.

Sample Input 2

5
5 4 4 5 4
1
1 5

Sample Output 2

14

Explanation for Sample 2

This sample input satisfies the constraints for Subtask 3.

Sample Input 3

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

Sample Output 3

277
227
72
262
178
181
174
257
208
262
262
113