시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB72272233.333%

## 문제

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

N ≤ 100, Q ≤ 100.

2 14

N ≤ 5 000.

3 27

N ≤ 200 000, Q = 1, L1 = 1, R1 = N.

4 54

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


## 채점 및 기타 정보

• 예제는 채점하지 않는다.