#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 1000000000000000000
#define MOD 1000000007
struct node {
int s, e, m, ab, c, abc, lz;
node *l, *r;
node(int _s, int _e) {
s = _s, e = _e, m = (s+e)/2, ab = c = abc = 0, lz = -1;
if(s != e) {
l = new node(s, m);
r = new node(m+1, e);
}
}
void prop() {
if(lz == -1) return;
ab = max(ab, lz);
abc = max(abc, ab+c);
if(s != e) {
l->lz = max(l->lz, lz);
r->lz = max(r->lz, lz);
}
lz = -1;
}
void update(int x, int y, int val) {
if(x > y) return;
prop();
if(x <= s && e <= y) {lz = max(val, lz); return;}
else if(x > m) r->update(x, y, val);
else if(y <= m) l->update(x, y, val);
else l->update(x, y, val), r->update(x, y, val);
l->prop(); r->prop();
abc = max(l->abc, r->abc);
}
void update2(int x, int val) {
if(s == e) {c = val; return;}
else if(x > m) r->update2(x, val);
else l->update2(x, val);
c = max(l->c, r->c);
}
int rmax(int x, int y) {
if(x > y) return -INF;
prop();
if(x <= s && e <= y) return abc;
else if(x > m) return r->rmax(x, y);
else if(y <= m) return l->rmax(x, y);
else return max(l->rmax(x, y), r->rmax(x, y));
}
} *root, *root2;
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n, q, x, y, idx;
cin >> n;
int a[n];
for(int i = 0; i < n; i++) cin >> a[i];
cin >> q;
tuple<int, int, int> qry[q];
int ans[q];
for(int i = 0; i < q; i++) {
cin >> x >> y;
x--; y--;
qry[i] = {x, y, i};
}
sort(qry, qry+q);
stack<int> s;
vector<pair<int, int>> good;
for(int i = 0; i < n; i++) {
while(s.size() && a[s.top()] <= a[i]) {
good.push_back({s.top(), i});
s.pop();
}
if(s.size()) good.push_back({s.top(), i});
s.push(i);
}
sort(good.begin(), good.end());
int gidx = good.size()-1, qidx = q-1;
root = new node(0, n-1);
for(int i = 0; i < n; i++) root->update2(i, a[i]);
for(int i = n-1; i >= 0; i--) {
while(gidx >= 0 && good[gidx].first == i) {
root->update(min(2*good[gidx].second-good[gidx].first, n), n-1, a[good[gidx].first] + a[good[gidx].second]);
gidx--;
}
while(qidx >= 0 && get<0>(qry[qidx]) == i) {
tie(x, y, idx) = qry[qidx];
ans[idx] = root->rmax(x, y);
qidx--;
}
}
for(int i = 0; i < q; i++) cout << ans[i] << '\n';
}
