#include<bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define mid ((l+r)>>1)
#define lc (id<<1)
#define rc (lc|1)
#define maxs(a,b) (a=max(a,b))
#define pb push_back
const int MXN = 5e5+5;
int n, q, a[MXN], L[MXN], R[MXN], ans[MXN];
vector<pii> Q[MXN];
vector<int> g[MXN];
int seg[MXN<<2], hseg[MXN<<2], lz[MXN<<2], hlz[MXN<<2];
inline void apply(int x, int id) {
maxs(hseg[id], seg[id]+=x);
maxs(hlz[id], lz[id]+=x);
}
inline void push(int id) {
maxs(hseg[lc], seg[lc]+hlz[id]);
seg[lc] += lz[id];
maxs(hlz[lc], lz[lc]+hlz[id]);
lz[lc] += lz[id];
maxs(hseg[rc], seg[rc]+hlz[id]);
seg[rc] += lz[id];
maxs(hlz[rc], lz[rc]+hlz[id]);
lz[rc] += lz[id];
hlz[id] = lz[id] = 0;
}
void upd(int s, int e, int x, int l=1, int r=n+1, int id=1) {
if(s<=l && r<=e) {
apply(x, id);
return;
}
push(id);
if(s<mid) upd(s, e, x, l, mid, lc);
if(e>mid) upd(s, e, x, mid, r, rc);
seg[id] = max(seg[lc], seg[rc]);
hseg[id] = max(hseg[lc], hseg[rc]);
}
int get(int s, int e, int l=1, int r=n+1, int id=1) {
if(s<=l && r<=e) return hseg[id];
push(id);
if(e<=mid) return get(s, e, l, mid, lc);
if(s>=mid) return get(s, e, mid, r, rc);
return max(get(s, e, l, mid, lc), get(s, e, mid, r, rc));
}
int32_t main() {
cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
cin >> n;
for(int i=1; i<=n; i++) {
cin >> a[i];
for(L[i]=i-1; L[i]&&a[L[i]]<a[i]; L[i]=L[L[i]]);
if(L[i]) g[L[i]].pb(i);
}
for(int i=n; i>=1; i--)
for(R[i]=i+1; R[i]<=n&&a[R[i]]<a[i]; R[i]=R[R[i]]);
cin >> q;
for(int i=1,l,r; i<=q; i++) {
cin >> l >> r;
Q[l].pb(pii(r, i));
}
for(int i=1; i<=n; i++) upd(i, i+1, a[i]);
for(int i=n; i>=1; i--) {
for(int j : g[i])
if(2*j-i<=n)
upd(2*j-i, n+1, a[i]+a[j]),
upd(2*j-i, n+1, -a[i]-a[j]);
if(2*R[i]-i<=n)
upd(2*R[i]-i, n+1, a[i]+a[R[i]]),
upd(2*R[i]-i, n+1, -a[i]-a[R[i]]);
for(auto [r, id] : Q[i])
ans[id] = get(i, r+1);
}
for(int i=1; i<=q; i++) cout << ans[i] << '\n';
return 0;
}
