题目描述

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

有一条很长的路，被划分为 $N$ 段并从 $1$ 到 $N$ 编号。每一段都一个坚固程度，第 $i$ 段路的坚固程度为 $A_i$。

JOI 君是一位有天赋的体育明星。他将在这条路上进行三级跳。一次三级跳包含三次连续的跳跃动作。设 $a,b,c$ 为 JOI 君进行三级跳时三个起跳点的所在段，那么需要满足以下条件：

• $a<b<c$。即：起跳点所在段需要严格递增；
• $b-a\le c-b$。即：第一次的跳跃距离应该不大于第二次的跳跃距离。

JOI 君将进行 $Q$ 次三级跳。第 $j$ 次三级跳的所有起跳点所在段编号都在 $L_j$ 到 $R_j$ 范围内。换句话说，必须保证 $L_j\le a<b<c\le R_j$。

JOI 君想在更坚固的段上起跳。对于每次三级跳，JOI 君想知道起跳点的最大坚固程度之和。

写一个程序，在给定路的段数和每次三级跳的信息的情况下，计算对于每次三级跳，起跳点的最大坚固程度之和。

输入格式

第一行一个整数 $N$，表示路的段数；

第二行 $N$ 个整数 $A_i$，第 $i$ 个数表示第 $i$ 段路的坚固程度；

第三行一个整数 $Q$，表示 JOI 君进行了 $Q$ 次三级跳；

接下来 $Q$ 行，每行两个整数 $L_j,R_j$，表示每次三段跳进行的区间。

输出格式

输出 $Q$ 行，第 $j\ (1\le j\le Q)$ 行表示对第 $j$ 个询问做出的回答。

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

数据范围与提示

对于所有数据，$3\le N\le 5\times 10^5,1\le Q\le 5\times 10^5,1\le A_i\le 10^9,1\le L_j\lt L_j+2\le R_j\le N$。

详细子任务附加限制及分值如下表：