Description
王神仙给你一个包含 n 个数的序列 w ,如果一个三元组 (a,b,c) 满足以下两个条件:
-
a<b<c
-
b−a⩽c−b
那么三元组(a,b,c) 是优秀的,再定义一个优秀的三元组 (a,b,c) 的权值为 wa+wb+wc 。
现在有q个询问,每次询问给出两个正整数 l,r 你需要求出满足 l⩽a<b<c⩽r 的优秀的三元组的最大权值。
第一行一个正整数n ,含义同题面描述。
第二行共n 个正整数,第 i 个表示 wi,含义同题面描述。
第三行一个正整数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⩽n⩽500000,1⩽q<=500000,1⩽wi⩽109,1⩽l<l+2⩽r⩽n
Subtask1(20pts):n,q⩽100
Subtask2(30pts):n⩽5000
Subtask3(20pts):n⩽200000,q=1
Subtask4(30pts):无限制