시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 3 3 3 100.000%

문제

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 ≤ i ≤ N) is Ai.

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 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 ≤ 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 ≤ j ≤ Q) triple jump, he should take off at sections whose numbers are in the range of Lj to Rj. In other words, Lj ≤ a < b < c ≤ Rj must be hold.

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.

입력

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

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

출력

Write Q lines to the standard output. The j-th (1 ≤ j ≤ Q) line should contain the maximum sum of firmness of the sections at which JOI-kun takes off in the j-th triple jump.

제한

  • 3 ≤ N ≤ 500 000.
  • 1 ≤ Ai ≤ 100 000 000 (1 ≤ i ≤ N).
  • 1 ≤ Q ≤ 500 000.
  • 1 ≤ Lj < Lj + 2 ≤ Rj ≤ N (1 ≤ j ≤ Q).

예제 입력 1

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

예제 출력 1

12
9
12

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 ≤ 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 ≤ c − b is not satisfied.

예제 입력 2

5
5 4 4 5 4
1
1 5

예제 출력 2

14

예제 입력 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

예제 출력 3

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