#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 5e5 + 5;
int n, nq, a[N], t[4 * N], lazy[4 * N], mx[4 * N], f[4 * N], ans[N];
vector <int> opt[N];
vector <pair<int, ii> > q;
stack <int> st;
void build(int i, int l, int r) {
if(l == r) {
mx[i] = a[l];
return ;
}
int mid = l + r >> 1;
build(i << 1, l, mid);
build(i << 1 | 1, mid + 1, r);
mx[i] = max(mx[i << 1], mx[i << 1 | 1]);
}
void down(int i) {
if(!down[i]) return ;
t[i << 1] = max(t[i << 1], lazy[i]);
f[i << 1] = max(f[i << 1], t[i << 1] + mx[i << 1]);
lazy[i << 1] = max(lazy[i << 1], lazy[i]);
t[i << 1 | 1] = max(t[i << 1 | 1], lazy[i]);
f[i << 1 | 1] = max(f[i << 1 | 1], t[i << 1 | 1] + mx[i << 1 | 1]);
lazy[i << 1 | 1] = max(lazy[i << 1 | 1], lazy[i]);
lazy[i] = 0;
}
void upd(int i, int l, int r, int u, int v, int val) {
if(l > v || u > r) return ;
if(u <= l && r <= v) {
t[i] = max(t[i], val);
lazy[i] = max(lazy[i], val);
f[i] = max(f[i], t[i] + mx[i]);
return ;
}
down(i);
int mid = l + r >> 1;
upd(i << 1, l, mid, u, v, val);
upd(i << 1 | 1, mid + 1, r, u, v, val);
f[i] = max(f[i << 1], f[i << 1 | 1]);
}
int get(int i, int l, int r, int u, int v) {
if(l > v || u > r) return 0;
if(u <= l && r <= v) return f[i];
down(i);
int mid = l + r >> 1;
return max(get(i << 1, l, mid, u, v) , get(i << 1 | 1, mid + 1, r, u, v));
}
main () {
cin.tie(0)->sync_with_stdio(0);
if(fopen("task.inp", "r")) {
freopen("task.inp", "r", stdin);
freopen("wa.out", "w", stdout);
}
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
build(1, 1, n);
for(int i = n; i >= 1; i--) {
while (!st.empty() && a[i] > a[st.top()]) {
opt[i].push_back(st.top());
st.pop();
}
if(!st.empty()) opt[i].push_back(st.top());
st.push(i);
}
cin >> nq;
for(int i = 1; i <= nq; i++) {
int l, r; cin >> l >> r;
q.push_back({i, {l, r}});
}
sort(q.begin(), q.end(), [] (pair<int, ii> x, pair<int, ii> y) {
return x.se.fi > y.se.fi;
});
int it = n;
for(int j = 0; j < nq; j++) {
int i = q[j].fi, l = q[j].se.fi, r = q[j].se.se;
while (it >= l) {
for(int b : opt[it]) upd(1, 1, n, 2 * b - it, n, a[it] + a[b]);
it--;
}
ans[i] = get(1, 1, n, l, r);
}
for(int i = 1; i <= nq; i++) cout << ans[i] << "\n";
}
