There is a very long straight road, which consists of sections numbered from through . Each section has specific firmness, and the firmness of the section is .
JOI-kun, the gifted sports star, is going to play triple jump. A triple jump consists of three consecutive jumps. Let be the numbers of sections at which JOI-kun takes off, then the following conditions should be met.
- . Namely, the numbers of the sections should be increasing.
- . 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 triple jumps. In the -th triple jump, he should take off at sections whose numbers are in the range of to . In other words, 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.
Output Specification
Write lines to the standard output. The -th line should contain the maximum sum of firmness of the sections at which JOI-kun takes off in the -th triple jump.
Constraints
- .
- .
- .
- .
Subtasks
- (5 points) , .
- (14 points) .
- (27 points) , , , .
- (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 by taking off at the sections , and .
In the second jump, JOI-kun can achieve the maximum sum of by taking off at the sections , and . If he takes off at the sections , and , the sum of firmness is , but is not satisfied.
In the third jump, JOI-kun can achieve the maximum sum of by taking off at the sections , and . If he takes off at the sections , and , the sum of firmness is , but 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
Comments