题目描述

译自 JOI Open 2019 T1 「三段跳び」

有一条路，包含 $N$ 段，编号 $1\sim N$。第 $i$ 段有一个强度 $A_i$。

JOI 君，有天赋的体育明星，准备来三段跳。一个三段跳包含三次连续的跳跃。令 $a,b,c$ 分别表示 JOI-kun 三次起跳的段编号，他们需要满足以下条件。

• $a<b<c$。含义是每次起跳的编号需要递增。
• $b-a\le c-b$。含义是第一次起跳跨越的距离需要小于等于第二次的。

JOI 君准备进行 $Q$ 次三段跳。在第 $j$ 次（$1\le j\le Q$）中，他需要在区间 $[L_j,R_j]$ 中的编号起跳，也就是要满足 $L_j\le a<b<c\le R_j$。

JOI 君 想要选择恰当的位置起跳。对于每次三段跳，JOI 君想知道他起跳的这些位置的强度和，最大是多少。

写一个程序，给定段数和三段跳的信息。对于每个三段跳，计算他起跳的这些位置的强度和，最大是多少。

输入格式

第 $1$ 行 $1$ 个整数 $N$。

第 $2$ 行 $N$ 个整数，代表 $A_1,A_2,\cdots,A_n$。

第 $3$ 行 $1$ 个整数 $Q$。

第 $4\sim 4+Q-1$ 行，每行两个整数 $L_i,R_i$。

输出格式

输出 $Q$ 行。每行输出一个整数，表示答案。

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

12
9
12

5
5 4 4 5 4
1
1 5

14

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

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

提示

样例解释：

在第一次跳跃中，JOI 君可以选择 $1,2,4$ 段，从而达到最大加和 $12$。

在第二次跳跃中，JOI 君可以选择 $3,4,5$ 段，从而达到最大加和 $9$。如果选择 $2,4,5$，虽然和是 $10$，但是 $b-a\le c-b$ 没有满足。

在第三次跳跃中，JOI 君可以选择 $1,2,4$ 段，从而达到最大加和 $12$。如果选择 $1,4,5$，虽然和是 $13$，但是 $b-a\le c-b$ 没有满足。

数据范围：

• $3 \le N \le 5 \times 10^5$。
• $1 \le A_i \le 10^8 (1 \le i \le N)$。
• $1 \le Q \le 5 \times 10^5$。
• $1 \le Lj < Lj + 2 \le Rj \le N (1 \le j \le Q)$。

子任务：

1. （5 分）$N\le 100$，$Q\le 100$。
2. （14 分）$N\le 5000$。
3. （27 分）$N\le 2\times 10^5$，$Q=1$，$L_1=1$，$R_1=N$。
4. （54 分）无额外约束。