题目描述

给定长度为 $n$ 的序列 $h$ 。

现在有 $q$ 次询问，每次给定整数 $l,r$ 满足 $1\le l\le r\le n$ ，我们称一个三元组 $(a,b,c)$ 是合法的，当且仅当它们满足以下条件：

1. $l\le a<b<c\le r$ 。

2. $b-a\le c-b$ 。

你希望求出所有合法三元组的 $h_a+h_b+h_c$ 的最大值。

输入格式

第一行输入一个整数 $n$ ，表示序列的长度。

第二行输入 $n$ 个整数，第 $i$ 个整数代表 $h_i$ 。

第三行输入一个整数 $q$ ，表示询问的次数。

接下来 $q$ 行，第 $i$ 行输入两个整数 $l_i,r_i$ ，表示一次询问的信息。

输出格式

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

样例

样例输入

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

样例输出

12
9
12

数据范围

对于所有数据，$3\le n\le 5*10^5,1\le q\le 5*10^5$ ；对于 $1\le i\le n$ ，$1\le h_i\le 10^9$ ；对于 $1\le i\le q$ ，$1\le l_i<l_i+2\le r_i\le n$ 。

子任务 1 ( 20% ) : $n,q\le 100$ 。

子任务 2 ( 40% ) : $n\le 5*10^3$。

子任务 3 ( 10% ) : $n\le 2*10^5,q=1,l_1=1,r_1=n$ 。

子任务 4 ( 30% ) : 无特殊限制。