#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
const int MAXN=5e5+10;
#define endl '\n'
struct Query {
int l;
int r;
int ind;
bool friend operator < (Query a, Query b) {
return a.l>b.l;
}
};
struct Jump {
int a;
int b;
int sum;
bool friend operator < (Jump a, Jump b) {
return a.a>b.a;
}
};
Query que[MAXN];
vector <Jump> v;
stack <int> st;
int tree[4*MAXN], lazy[4*MAXN], mx[4*MAXN];
int a[MAXN], ans[MAXN];
void build_tree(int node, int l, int r) {
lazy[node]=0;
if (l==r) {
tree[node]=a[l];
mx[node]=a[l];
return;
}
int mid=(l+r)/2;
build_tree(node*2,l,mid);
build_tree(node*2+1,mid+1,r);
tree[node]=max(tree[node*2],tree[node*2+1]);
mx[node]=tree[node];
}
void add_lazy(int node, int ch) {
if (ch<=lazy[node]) return;
lazy[node]=ch;
tree[node]=max(tree[node],mx[node]+ch);
}
void push_lazy(int node, int l, int r) {
if (l!=r) {
add_lazy(node*2,lazy[node]);
add_lazy(node*2+1,lazy[node]);
}
lazy[node]=0;
}
void update(int node, int l, int r, int ql, int qr, int ch) {
if (ql>r || qr<l) return;
push_lazy(node,l,r);
if (l>=ql && r<=qr) {
add_lazy(node,ch);
return;
}
int mid=(l+r)/2;
update(node*2,l,mid,ql,qr,ch);
update(node*2+1,mid+1,r,ql,qr,ch);
tree[node]=max(tree[node*2],tree[node*2+1]);
}
int query(int node, int l, int r, int ql, int qr) {
if (ql>r || qr<l) return 0;
push_lazy(node,l,r);
if (l>=ql && r<=qr) {
//cout << l << ' ' << r << ' ' << tree[node] << endl;
return tree[node];
}
int mid=(l+r)/2;
return max(query(node*2,l,mid,ql,qr),query(node*2+1,mid+1,r,ql,qr));
}
int main () {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n;
for (int i=1;i<=n;i++) {
cin >> a[i];
while (!st.empty() && a[i]>a[st.top()]) st.pop();
if (!st.empty()) v.push_back({st.top(),i,a[i]+a[st.top()]});
st.push(i);
}
while (!st.empty()) st.pop();
for (int i=n;i>=1;i--) {
while (!st.empty() && a[i]>a[st.top()]) st.pop();
if (!st.empty()) v.push_back({i,st.top(),a[i]+a[st.top()]});
st.push(i);
}
sort(v.begin(),v.end());
cin >> q;
for (int i=0;i<q;i++) {
cin >> que[i].l >> que[i].r;
que[i].ind=i;
}
sort(que,que+q);
int curq, curv;
curq=curv=0;
build_tree(1,1,n);
for (int i=n-2;i>=1;i--) {
while (curv<v.size() && v[curv].a>=i) {
int gr=v[curv].b*2-v[curv].a;
if (gr<=n) {
//cout << v[curv].a << ' ' << v[curv].b << ' ' << gr << endl;
update(1,1,n,gr,n,v[curv].sum);
}
curv++;
}
while (curq<q && que[curq].l==i) {
ans[que[curq].ind]=query(1,1,n,que[curq].l,que[curq].r);
curq++;
}
if (curq==q) break;
}
for (int i=0;i<q;i++) cout << ans[i] << endl;
return 0;
}
