有一条很长的笔直道路，由 $N$ 个路段组成，编号为 $1$ 到 $N$。每个路段都有特定的坚固度，第 $i$ 个路段（$1 \le i \le N$）的坚固度为 $A_i$。

JOI-kun 是一位天才运动员，他准备进行三级跳远。三级跳远由三次连续的跳跃组成。设 JOI-kun 起跳的路段编号分别为 $a, b, c$，则必须满足以下条件：

• $a < b < c$。即路段编号必须递增。
• $b - a \le c - b$。即第一次跳跃的距离必须小于或等于第二次跳跃的距离。

JOI-kun 将进行 $Q$ 次三级跳远。在第 $j$ 次（$1 \le j \le Q$）三级跳远中，他起跳的路段编号必须在 $L_j$ 到 $R_j$ 的范围内。换句话说，必须满足 $L_j \le a < b < c \le R_j$。

JOI-kun 希望在更坚固的路段起跳。对于每次三级跳远，JOI-kun 想知道他起跳路段的坚固度之和的最大值。

请编写一个程序，在给定路段数量和三级跳远信息的情况下，计算每次三级跳远中起跳路段坚固度之和的最大值。

输入格式

从标准输入读取以下数据。所有输入值均为整数。

$N$ $A_1 \ A_2 \ \dots \ A_N$ $Q$ $L_1 \ R_1$ $L_2 \ R_2$ $\vdots$ $L_Q \ R_Q$

输出格式

向标准输出写入 $Q$ 行。第 $j$ 行（$1 \le j \le Q$）应包含第 $j$ 次三级跳远中起跳路段坚固度之和的最大值。

数据范围

• $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$)

子任务

1. (5 分) $N \le 100, Q \le 100$
2. (14 分) $N \le 5\,000$
3. (27 分) $N \le 200\,000, Q = 1, L_1 = 1, R_1 = N$
4. (54 分) 无附加限制

样例

样例输入 1

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

样例输出 1

12
9
12

说明

在第一次跳跃中，JOI-kun 可以通过在路段 1、2 和 4 起跳获得最大和 12。 在第二次跳跃中，JOI-kun 可以通过在路段 3、4 和 5 起跳获得最大和 9。如果他在路段 2、4 和 5 起跳，坚固度之和为 10，但不满足 $b - a \le c - b$。 在第三次跳跃中，JOI-kun 可以通过在路段 1、2 和 4 起跳获得最大和 12。如果他在路段 1、4 和 5 起跳，坚固度之和为 13，但不满足 $b - a \le c - b$。

样例输入 2

5
5 4 4 5 4
1
1 5

样例输出 2

14

说明

该样例输入满足子任务 3 的限制。

样例输入 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