#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5e5+10;
const ll oo = 1e18;
int n;
ll a[N];
deque<pair<int,int>>q;
vector<pair<int,int>> rel;
struct data{
ll ab, c, sum;
data(ll x = -oo,ll y = -oo, ll z = -oo) {
ab = x, c = y, sum = z;
}
}t[N<<2];
data merge(data L, data R) {
return data({max(L.ab, R.ab), max(L.c, R.c), max({L.sum, R.sum, L.ab + R.c})});
}
void updAB(int node, int L, int R, int pos, ll x) {
if(L == R) {
t[node].ab = max(t[node].ab, x);
t[node].sum = t[node].ab + t[node].c;
return;
} int mid = (L + R) >> 1, lc = node << 1, rc = lc | 1;
if(pos <= mid) updAB(lc, L, mid, pos, x);
else updAB(rc, mid + 1, R, pos, x);
t[node] = merge(t[lc], t[rc]);
}
void updC(int node, int L, int R, int pos, ll x) {
if(L == R) {
t[node].c = x;
t[node].sum = t[node].ab + t[node].c;
return;
} int mid = (L + R) >> 1, lc = node << 1, rc = lc | 1;
if(pos <= mid) updC(lc, L, mid, pos, x);
else updC(rc, mid + 1, R, pos, x);
t[node] = merge(t[lc], t[rc]);
}
data get(int node, int L, int R, int l, int r) {
if(r < L || R < l) return data();
if(l <= L && R <= r) return t[node];
int mid = (L + R) >> 1, lc = node << 1, rc = lc | 1;
data le = get(lc, L, mid, l, r);
data ri = get(rc, mid + 1, R, l, r);
return merge(le, ri);
}
vector<pair<int,int>> off[N];
vector<int> candi[N];
ll ans[N];
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%lld", &a[i]);
q.push_back({INT_MAX, -1});
for(int i = 1; i <= n; i++) {
while(q.back().first < a[i]) {
rel.push_back({q.back().second, i});
q.pop_back();
}
if(q.back().second + 1) rel.push_back({q.back().second, i});
q.push_back({a[i], i});
}
for(auto it : rel) candi[it.first].push_back(it.second);
int m; scanf("%d", &m);
for(int i = 0; i < m; i++) {
int l, r; scanf("%d %d", &l, &r);
off[l].push_back({r, i});
}
for(int i = n; i > 0; i--) {
updC(1, 1, n, i, a[i]);
for(auto it : candi[i]) if(2 * it - i <= n) updAB(1, 1, n, 2 * it - i, a[i] + a[it]);
for(auto qu : off[i]) ans[qu.second] = get(1, 1, n, i, qu.first).sum;
}
for(int i = 0; i < m; i++)
printf("%lld\n", ans[i]);
return 0;
}
