JOI '19 Open P1 - Triple Jump

View as PDF

Submit solution

Points: 30 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem type

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

Comments

There are no comments at the moment.