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~

~\vdots~

~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 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)~.

Subtasks

1. (5 points) ~N \le 100~, ~Q \le 100~.
2. (14 points) ~N \le 5\,000~.
3. (27 points) ~N \le 200\,000~, ~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