#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
#define endl '\n'
#define pi pair<int, int>
#define pii pair<int, pi>
#define f first
#define s second
struct segTree{
int l, r;
segTree *left, *right;
pii val = {0, {0, 0}};
segTree(int a, int b){
l = a;
r = b;
if(l != r){
int mid = (l + r) / 2;
left = new segTree(l, mid);
right = new segTree(mid + 1, r);
}
}
void add(int x, pi v){
if(x < l || r < x) return;
if(l == r){
val.s.f = max(val.s.f, v.f);
val.s.s = max(val.s.s, v.s);
val.f = val.s.f + val.s.s;
return;
}
left->add(x, v);
right->add(x, v);
val.f = max(left->val.s.f + right->val.s.s, max(left->val.f, right->val.f));
val.s.f = max(left->val.s.f, right->val.s.f);
val.s.s = max(left->val.s.s, right->val.s.s);
}
pii qry(int a, int b){
if(r < a || b < l) return {0, {0, 0}};
if(a <= l && r <= b) return val;
pii lq = left->qry(a, b), rq = right->qry(a, b);
return {max(lq.s.f + rq.s.s, max(lq.f, rq.f)), {max(lq.s.f, rq.s.f), max(lq.s.s, rq.s.s)}};
}
};
const int maxn = 500000;
int n, q;
int a[maxn], b[maxn];
vector<int> p[maxn];
vector<pi> qry[maxn];
int ans[maxn];
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
stack<int> stk;
for(int i = 0; i < n; i++){
cin >> a[i];
while(!stk.empty()){
int j = stk.top(), k = 2 * i - j;
if(k < n) p[j].push_back(k);
if(a[j] <= a[i]) stk.pop();
else break;
}
stk.push(i);
}
cin >> q;
for(int i = 0; i < q; i++){
int l, r;
cin >> l >> r;
l--, r--;
qry[l].push_back({r, i});
}
segTree tre(0, n);
for(int i = n - 1; i >= 0; i--){
tre.add(i, {0, a[i]});
for(int j : p[i]) tre.add(j, {a[i] + a[(i + j) / 2], 0});
for(pi j : qry[i]) ans[j.s] = tre.qry(i, j.f).f;
}
for(int i = 0; i < q; i++) cout << ans[i] << endl;
return 0;
}
