#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
struct node { int v, f, a; } T[1050000];
const node EMP = {0, 0, 0};
node operator +(node L, node R) {
node ret;
ret.f = max(L.f, R.f);
ret.a = max(L.a, R.a);
ret.v = max({L.v, R.v, L.f + R.a});
return ret;
}
int A[500009], ans[500009], F[500009];
vector<pii> query[500009];
vector<int> add[500009];
void init(int idx, int s, int e) {
if(s == e) {
T[idx] = {A[s], 0, A[s]};
return;
}
int m = s+e >> 1;
init(idx*2, s, m);
init(idx*2+1, m+1, e);
T[idx] = T[idx*2] + T[idx*2+1];
}
void upd(int idx, int s, int e, int p, int v) {
if(p < s || e < p) return;
if(s == e) {
T[idx].f = v;
T[idx].v = T[idx].f + T[idx].a;
return;
}
int m = s+e >> 1;
upd(idx*2, s, m, p, v);
upd(idx*2+1, m+1, e, p, v);
T[idx] = T[idx*2] + T[idx*2+1];
}
node get(int idx, int s, int e, int l, int r) {
if(r < s || e < l) return EMP;
if(l <= s && e <= r) return T[idx];
int m = s+e >> 1;
return get(idx*2, s, m, l, r) + get(idx*2+1, m+1, e, l, r);
}
int main() {
int N; scanf("%d", &N);
for(int i=1; i<=N; i++) scanf("%d", &A[i]);
int Q; scanf("%d", &Q);
for(int i=0; i<Q; i++) {
int l, r; scanf("%d%d",&l,&r);
query[l].push_back({r, i});
}
vector<int> S;
for(int i=1; i<=N; i++) {
while(S.size() && A[S.back()] < A[i]) {
add[S.back()].push_back(i);
S.pop_back();
}
if(S.size()) add[S.back()].push_back(i);
S.push_back(i);
}
init(1, 1, N);
for(int i=N; i>=1; i--) {
for(auto& it: add[i]) if(2*it - i <= N) {
F[2*it - i] = max(F[2*it - i], A[i] + A[it]);
upd(1, 1, N, 2*it - i, F[2*it - i]);
}
for(auto& it: query[i]) ans[it.second] = get(1, 1, N, i, it.first).v;
}
for(int i=0; i<Q; i++) printf("%d\n", ans[i]);
return 0;
}
