#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct st_node {
ll mxv, mx;
ll lz;
};
const int MAXN = 5e5+5;
const ll INF = 1e18;
int input[MAXN];
vector<tuple<int, int, int> > qv; //{r, l, id}
vector<tuple<int, int, int> > jumps; //{r, l, val}
st_node seg[MAXN*4];
ll ans[MAXN];
int n, q;
void st_process() {
stack<int> st;
input[0] = 2e9;
st.push(0);
for(int i = 1; i <= n; i++) {
while(input[st.top()] < input[i]) st.pop();
if(st.top() != 0) {
int id = st.top();
jumps.push_back({ i+i-id, id, input[i]+input[id] });
}
st.push(i);
}
while(st.size()) st.pop();
input[n+1] = 2e9;
st.push(n+1);
for(int i = n; i >= 1; i--) {
while(input[st.top()] < input[i]) st.pop();
if(st.top() != n+1) {
int id = st.top();
jumps.push_back({ id+id-i, i, input[i]+input[id] });
}
st.push(i);
}
sort(jumps.begin(), jumps.end());
}
void refresh(int u, int l, int r) {
ll val = seg[u].lz;
seg[u].lz = 0;
seg[u].mx = max(seg[u].mx, seg[u].mxv+val);
if(l == r) return;
int vl = u*2;
int vr = vl|1;
seg[vl].lz = max(seg[vl].lz, val);
seg[vr].lz = max(seg[vr].lz, val);
}
ll query(int u, int l, int r, int ql, int qr) {
refresh(u, l, r);
if(ql > r || qr < l) return -INF;
if(ql <= l && qr >= r) return seg[u].mx;
int m = (l+r)/2;
int vl = u*2;
int vr = vl|1;
return max( query(vl, l, m, ql, qr), query(vr, m+1, r, ql, qr) );
}
void update(int u, int l, int r, int ql, int qr, ll val) {
refresh(u, l, r);
if(ql > r || qr < l) return;
if(ql <= l && qr >= r) {
seg[u].lz = val;
refresh(u, l, r);
return;
}
int m = (l+r)/2;
int vl = u*2;
int vr = vl|1;
update(vl, l, m, ql, qr, val);
update(vr, m+1, r, ql, qr, val);
seg[u].mx = max(seg[vl].mx, seg[vr].mx);
seg[u].mxv = max(seg[vl].mxv, seg[vr].mxv);
}
void build(int u, int l, int r) {
seg[u].mx = seg[u].mxv = -INF;
if(l == r) return;
int m = (l+r)/2;
int vl = u*2;
int vr = vl|1;
build(vl, l, m);
build(vr, m+1, r);
}
void activate(int u, int l, int r, int qi, ll val) {
refresh(u, l, r);
if(qi < l || qi > r) return;
if(l == r) {
seg[u].mxv = max(seg[u].mxv, val);
seg[u].mx = max(seg[u].mx, val);
return;
}
int m = (l+r)/2;
int vl = u*2;
int vr = vl|1;
activate(vl, l, m, qi, val);
activate(vr, m+1, r, qi, val);
seg[u].mx = max(seg[vl].mx, seg[vr].mx);
seg[u].mxv = max(seg[vl].mxv, seg[vr].mxv);
}
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &input[i]);
scanf("%d", &q);
for(int i = 1; i <= q; i++) {
int a, b;
scanf("%d %d", &a, &b);
qv.push_back({b, a, i});
}
sort(qv.begin(), qv.end());
st_process();
// for(auto jump : jumps) printf("%d %d %d\n", get<0>(jump), get<1>(jump), get<2>(jump));
build(1, 1, n);
int pj = 0, pq = 0;
for(int i = 1; i <= n; i++) {
while(pj < jumps.size() && get<0>(jumps[pj]) <= i) {
int l, r, val;
tie(r, l, val) = jumps[pj];
// printf("activate %d %d\n", l, val);
activate(1, 1, n, l, val);
pj++;
}
update(1, 1, n, 1, n, input[i]);
// printf("upd %d\n", input[i]);
// printf("ans %d...\n", i);
while(pq < qv.size() && get<0>(qv[pq]) <= i) {
int l, r, id;
tie(r, l, id) = qv[pq];
ans[id] = query(1, 1, n, l, r);
pq++;
}
}
for(int i = 1; i <= q; i++) printf("%lld\n", ans[i]);
}
