三级跳

给定一个长度为 $N$ 的序列 $A_1, A_2, \ldots, A_N$。

对于一次操作，需要选择三个整数 $a,b,c$，满足：

• $a < b < c$；
• $b - a \le c - b$。

现有 $Q$ 次询问。第 $j$ 次询问给出两个整数 $L_j, R_j$，要求所选的 $a,b,c$ 满足

$$L_j \le a < b < c \le R_j.$$

对于每次询问，求

$$A_a + A_b + A_c$$

的最大值。

输入格式

第一行一个整数 $N$。

第二行 $N$ 个整数 $A_1, A_2, \ldots, A_N$。

第三行一个整数 $Q$。

接下来 $Q$ 行，每行两个整数 $L_j, R_j$，表示一组询问。

输出格式

输出 $Q$ 行。

第 $j$ 行输出一个整数，表示第 $j$ 次询问的最大值。

提示

对于前 20% 的数据，$N,Q \le 500$。

对于前 40% 的数据，$N,Q \le 5000$。

对于另外 20% 的数据，$N \le 500000$，$Q=1$，且 $L_1=1,R_1=N$。

对于另外 20% 的数据，$A_i$ 在值域内随机生成。

对于 100% 的数据，$3 \le N \le 500000$，$1 \le Q \le 500000$，$1 \le A_i \le 10^9$，$1 \le L_j \le R_j \le N$，并保证 $R_j - L_j + 1 \ge 3$。