Description

王神仙给你一个包含 $n$ 个数的序列 $w$ ，如果一个三元组 $(a,b,c)$ 满足以下两个条件：

1. $a<b<c$

2. $b-a \leqslant c-b$

那么三元组$(a,b,c)$ 是优秀的，再定义一个优秀的三元组 $(a,b,c)$ 的权值为 $w_a+w_b+w_c$ 。

现在有$q$个询问，每次询问给出两个正整数 $l,r$ 你需要求出满足 $l \leqslant a<b<c \leqslant r$ 的优秀的三元组的最大权值。

Format

Input

第一行一个正整数$n$ ，含义同题面描述。

第二行共$n$ 个正整数，第 $i$ 个表示 $w_i$，含义同题面描述。

第三行一个正整数$q$ ，表示询问个数。

接下来$q$ 行每行两个正整数 $l,r$ ，含义同题面描述。

Output

输出共$q$ 行，第 $i$ 行一个正整数表示第 $i$ 个询问的答案。

Samples

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

12
9
12

hint

对于第一个询问权值最大的三元组是$(1,2,4)$

对于第二个询问权值最大的三元组是$(3,4,5)$

对于第三个询问权值最大的三元组是$(1,2,4)$

Limitation

对于所有数据：$3 \leqslant n \leqslant 500000,1 \leqslant q<=500000,1 \leqslant w_i \leqslant 10^9,1 \leqslant l<l+2 \leqslant r \leqslant n $

Subtask1(20pts):$n,q \leqslant 100$

Subtask2(30pts):$n \leqslant 5000$

Subtask3(20pts):$n \leqslant 200000,q=1$

Subtask4(30pts):无限制