#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i = a ; i <= b ; ++i)
#define X first
#define Y second
#define pb push_back
#define ll long long
#define lch i << 1
#define rch i << 1 | 1
#define Unit Node(-2e9,-2e9,-3e9)
const int N = 5e5 + 1;
typedef pair<int,int> ii;
struct Node {
ll L, R, S;
Node(ll l = 0,ll r = 0,ll s = 0) : L(l), R(r), S(s) {}
} tr[N << 2];
Node Spare;
Node operator + (const Node &a,const Node &b) {
ll x = max(a.L,b.L);
ll y = max(a.R,b.R);
ll z = max(a.S,b.S);
return Node(x,y,max(z,a.L + b.R));
}
void upd(int i,int l,int r,int p,int v,int t) {
if (l > p) return;
if (r < p) return;
if (l == r) {
if (t) tr[i].R = max(tr[i].R,(ll)v);
else tr[i].L = max(tr[i].L,(ll)v);
tr[i].S = tr[i].L + tr[i].R;
return;
}
int m = (l + r) / 2;
upd(lch,l,m,p,v,t); ++m;
upd(rch,m,r,p,v,t);
tr[i] = tr[lch] + tr[rch];
}
void get(int i,int l,int r,int L,int R) {
if (l > R) return;
if (L > r) return;
if (L <= l && r <= R) {
Spare = Spare + tr[i];
return;
}
int m = (l + r) / 2;
get(lch,l,m,L,R); ++m;
get(rch,m,r,L,R);
}
vector<ii> Que[N];
vector<ii> Seg[N];
int a[N];
int t[N];
int tot = 0;
ll ans[N];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n; cin >> n;
fill(tr + 1,tr + 4 * n,Unit);
auto add = [&](int x,int y) {
if (y + y <= n + x)
Seg[x].pb(ii(y + y - x,a[x] + a[y]));
};
auto ask = [&](int l,int r) {
Spare = Unit;
get(1,1,n,l,r);
return Spare.S;
};
FOR(i,1,n) {
cin >> a[i];
for(; tot && a[t[tot]] < a[i] ; --tot)
add(t[tot],i);
if (tot)
add(t[tot],i);
t[++tot] = i;
}
int q; cin >> q;
FOR(i,1,q) {
int l; cin >> l;
int r; cin >> r;
Que[l].push_back(ii(r,i));
}
for(int i = n ; i >= 1 ; --i) {
upd(1,1,n,i,a[i],1);
for(ii e : Seg[i])
upd(1,1,n,e.X,e.Y,0);
for(ii e : Que[i])
ans[e.Y] = ask(i,e.X);
}
FOR(i,1,q) cout << ans[i] << "\n";
}
/*
5
5 2 1 5 3
3
1 4
2 5
1 5
*/
