题意描述

在地球上，时间可以理解为是一个一维的数轴（一个序列）。一个时间节点上的蝴蝶效应可以理解为是一个正整数。由于一开始已经进行了一些操作，所以第 $i$ 个时间节点上的蝴蝶效应为一个正整数 $v_i$。

具体来说，小$\text{W}$ 将会做出 $q$ 次「预言」。一次「预言」需要两个参数 $l,r$，表示需要从区间 $[l,r]$ 中选择三个不同的时间节点 $l\le a\lt b\lt c\le r$，但是由于技术不成熟，三个时间节点还要求 $b-a\le c-b$。且一次「预言」的评估值为选中的三个时间节点上的蝴蝶效应的累加和即 $v_a+v_b+v_c$。由于形势迫在眉睫，小$\text{W}$ 希望评估值尽可能大。

可是 小$\text{W}$ 不会解决这个问题，为了帮助她成为救世主，你需要告诉她每次「预言」可能的评估值的最大值。

输入格式

第一行一个正整数 $n\ (1\le n\le 5\times 10^5)$ 表示时间轴的长度。

第二行 $n$ 个正整数 $a_i\ (1\le a_i \le 10^8)$ 表示初始时第 $i$ 个时间节点上的蝴蝶效应。

第三行一个整数 $q\ (1\le q\le 5\times 10^5)$ 表示「预言」的次数。

接下来第 $4$ 至 $q+3$ 行，每行两个整数 $l,r\ (1\le l\le r\le n)$，表示 小$\text{W}$ 向你询问一次「预言」操作的最大评估值。

输出格式

$q$ 行表示每次「预言」的可能评估值的最大值。

样例

样例输入 #1

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

样例输出 #1

12
9
12

样例输入 #2

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

样例输出 #2

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

说明 / 提示

对于 $15\%$ 的数据，$1\le n,q \le 10^2$。

对于 $30\%$ 的数据，$1\le n,q \le 5 \times 10^3$。

对于另外 $15\%$ 的数据，$1\le n\le 2\times 10^5,q=l=1,r=n$。

对于 $100\%$ 的数据，$1\le n,q \le 5 \times 10 ^ 5,1\le l\le r\le n$。