#include <bits/stdc++.h>
using namespace std;
typedef pair<long long,long long> ii;
const long long inf = 40000000003LL;
struct node{
long long c;
long long ab;
long long abc;
};
const long long N = 1 << 19; ///change to 1 << 19 upon submitting
static node tree[2*N+5];
static long long arr[N+5];
node relax(node x, node y){
node z;
z.c = max(x.c, y.c);
z.ab = max(x.ab, y.ab);
z.abc = max(x.ab + y.c, max(x.abc,y.abc));
return z;
}
void init(){
for(long long i = N;i < 2*N;i++){
tree[i] = {arr[i-N],-inf,-inf};
}
for(long long i = N-1;i > 0;i--){
tree[i] = relax(tree[i<<1],tree[i<<1|1]);
}
}
void update(long long i, long long v){
i += N;
tree[i].ab = max(tree[i].ab,v);
tree[i].abc = max(tree[i].abc,tree[i].ab+tree[i].c);
while(i > 1){
i >>= 1;
tree[i] = relax(tree[i<<1],tree[i<<1|1]);
}
}
long long query(long long l, long long r){
node L = {-inf,-inf,-inf};
node R = {-inf,-inf,-inf};
for(l += N, r += N;l < r;l >>= 1, r >>= 1){
if(l&1){
L = relax(L,tree[l]);
l++;
}
if(r&1){
r--;
R = relax(tree[r],R);
}
}
return relax(L,R).abc;
}
int main(){
//freopen("i.txt","r",stdin);
ios_base::sync_with_stdio(false);
cin.tie(0);
long long n;
cin >> n;
for(long long i = 0;i < n;i++) cin >> arr[i];
vector<long long> critical[n];
vector<ii> queries[n];
stack<long long> s;
for(long long b = 0;b < n;b++){
while(!s.empty() && arr[b] >= arr[s.top()]){
long long a = s.top();
long long c = 2 * b - a;
if(c < n) critical[a].push_back(c);
s.pop();
}
if(!s.empty()){
long long a = s.top();
long long c = 2 * b - a;
if(c < n) critical[a].push_back(c);
}
s.push(b);
}
long long q; cin >> q;
long long answer[q];
for(long long i = 0;i < q;i++){
long long l, r; cin >> l >> r;
queries[l-1].push_back(ii(r-1,i));
}
init();
for(long long l = n-1;l >= 0;l--){
long long a = l;
for(long long ab : critical[a]){
long long b = (a + ab) / 2;
update(ab, arr[a] + arr[b]);
}
for(ii Q : queries[l]){
long long r = Q.first;
answer[Q.second] = query(l, r+1);
}
}
for(long long i = 0;i < q;i++) cout << answer[i] << "\n";
return 0;
}
