#include<bits/stdc++.h> using namespace std; const int MAXN=5e5+5; int L[MAXN],R[MAXN],A[MAXN],ans[MAXN],seg[MAXN*4],lazy[MAXN*4],F[MAXN*4]; vector<int> vi[MAXN]; vector< pair<int,int> > vq[MAXN]; void build(int l,int r,int pos) { if(l==r) { F[pos]=seg[pos]=A[l]; return ; } int mid=(l+r)/2; build(l,mid,pos*2); build(mid+1,r,pos*2+1); F[pos]=seg[pos]=max(F[pos*2],F[pos*2+1]); } void down(int pos) { int val=lazy[pos]; seg[pos*2]=max(seg[pos*2],val+F[pos*2]); seg[pos*2+1]=max(seg[pos*2+1],val+F[pos*2+1]); lazy[pos*2]=max(lazy[pos*2],val); lazy[pos*2+1]=max(lazy[pos*2+1],val); lazy[pos]=0; } void update(int l,int r,int u,int v,int val,int pos) { if(v<l||r<u) return ; if(u<=l&&r<=v) { seg[pos]=max(seg[pos],val+F[pos]); lazy[pos]=max(lazy[pos],val); return ; } int mid=(l+r)/2; down(pos); update(l,mid,u,v,val,pos*2); update(mid+1,r,u,v,val,pos*2+1); seg[pos]=max(seg[pos*2],seg[pos*2+1]); } int get(int l,int r,int u,int v,int pos) { if(u<=l&&r<=v) return seg[pos]; int mid=(l+r)/2; down(pos); if(v<=mid) return get(l,mid,u,v,pos*2); if(mid+1<=u) return get(mid+1,r,u,v,pos*2+1); return max(get(l,mid,u,v,pos*2),get(mid+1,r,u,v,pos*2+1)); } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,q; cin>>n; for(int i=1;i<=n;i++) cin>>A[i]; stack<int> st; for(int i=1;i<=n;i++) { while(!st.empty()&&A[i]>A[st.top()]) st.pop(); if(st.empty()) L[i]=-1; else L[i]=st.top(); st.push(i); } while(!st.empty()) st.pop(); for(int i=n;i;i--) { while(!st.empty()&&A[i]>=A[st.top()]) st.pop(); if(st.empty()) R[i]=-1; else R[i]=st.top(); st.push(i); } for(int i=1;i<=n;i++) { if(L[i]!=-1) vi[L[i]].push_back(i); if(R[i]!=-1) vi[i].push_back(R[i]); } build(1,n,1); cin>>q; for(int i=1;i<=q;i++) { int l,r; cin>>l>>r; vq[l].push_back({r,i}); } for(int i=n;i;i--) { for(auto v:vi[i]) update(1,n,v*2-i,n,A[i]+A[v],1); for(auto v:vq[i]) ans[v.second]=get(1,n,i,v.first,1); } for(int i=1;i<=q;i++) cout<<ans[i]<<"\n"; }