#include<bits/stdc++.h>
using namespace std;
typedef long long int lld;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
class ST{
lld tree[4000000];
public:
void build(int a, int b, int node){
if(a==b){
tree[node]=0;
return;
}
int mid=(a+b)/2;
build(a,mid,2*node);
build(mid+1,b,2*node+1);
tree[node]=max(tree[node*2],tree[node*2+1]);
}
void update(int a, int b, int node, int pos, lld val){
if(pos<a || b<pos)return;
if(a==b){
tree[node]=val;
return;
}
int mid=(a+b)/2;
update(a,mid,2*node,pos,val);
update(mid+1,b,2*node+1,pos,val);
tree[node]=max(tree[node*2],tree[node*2+1]);
}
lld query(int a, int b, int node, int x, int y){
if(x>y)return -100000000000;
if(b<x || y<a)return -100000000000;
if(x<=a && b<=y)return tree[node];
int mid=(a+b)/2;
return max(query(a,mid,2*node,x,y),query(mid+1,b,2*node+1,x,y));
}
};
class ST2{
lld tree[4000000];
lld lazy[4000000];
lld Historic[4000000];
lld Historic_lazy[1000000];
public:
void build(int a, int b, int node){
Historic_lazy[node]=0;
lazy[node]=0;
if(a==b){
tree[node]=0;
Historic[node]=0;
return;
}
int mid=(a+b)/2;
build(a,mid,2*node);
build(mid+1,b,2*node+1);
tree[node]=max(tree[2*node],tree[2*node+1]);
Historic[node]=0;
Historic[node]=max(Historic[node],tree[node]);
}
void propagate(int a, int b, int node){
Historic[node]=max(Historic[node],tree[node]+Historic_lazy[node]);
tree[node]+=lazy[node];
if(a!=b){
Historic_lazy[2*node]=max(Historic_lazy[2*node],lazy[2*node]+Historic_lazy[node]);
lazy[2*node]+=lazy[node];
Historic_lazy[2*node+1]=max(Historic_lazy[2*node+1],lazy[2*node+1]+Historic_lazy[node]);
lazy[2*node+1]+=lazy[node];
}
lazy[node]=0;
Historic_lazy[node]=0;
}
void update(int a, int b, int node,int x, int y, lld val){
propagate(a,b,node);
if(y<a || b<x)return;
if(x<=a && b<=y){
lazy[node]+=val;
Historic_lazy[node]=max(lazy[node],Historic_lazy[node]);
propagate(a,b,node);
return;
}
int mid=(a+b)/2;
update(a,mid,2*node,x,y,val);
update(mid+1,b,2*node+1,x,y,val);
tree[node]=max(tree[2*node],tree[2*node+1]);
Historic[node]=max(Historic[2*node],Historic[2*node+1]);
}
lld query(int a, int b, int node, int x, int y){
propagate(a,b,node);
if(y<a || b<x)return -1000000000;
if(x<=a && b<=y)return Historic[node];
int mid=(a+b)/2;
return max(query(a,mid,2*node,x,y),query(mid+1,b,2*node+1,x,y));
}
void print(int a, int b, int node){
cout<<a<<" "<<b<<" "<<tree[node]<<" "<<Historic[node]<<" "<<lazy[node]<<" "<<Historic_lazy[node]<<endl;
if(a==b)return;
int mid=(a+b)/2;
print(a,mid,2*node);
print(mid+1,b,2*node+1);
}
};
int main(){
srand(time(NULL));
int n,q;
scanf("%d",&n);
lld arr[n];
rep(i,0,n){
scanf("%lld",&arr[i]);
//arr[i]=rand()%100;
}
scanf("%d",&q);
vector<pair<int,int> > Queries[n];
rep(i,0,q){
int l,r;
scanf("%d %d",&l,&r);
l--;r--;
Queries[l].push_back(pair<int,int>(r,i));
}
ST *S=new ST();
S->build(0,n-1,1);
rep(i,0,n)S->update(0,n-1,1,i,arr[i]);
set<int> candidates;
vector<int> V[n];
for(int i=n-1;i>-1;i--){
queue<int> eliminate;
for(set<int>::iterator it=candidates.begin();it!=candidates.end();it++){
//cout<<a<<" "<<i<<" "<<S->query(0,n-1,1,i+1,a-1)<<endl;
int a=*it;
if(S->query(0,n-1,1,i+1,a-1)<min(arr[i],arr[a])){
V[i].push_back(a);
}
if(S->query(0,n-1,1,i+1,a-1)>arr[i]){
it=candidates.end();
it--;
}
if(S->query(0,n-1,1,i+1,a-1)>arr[a]){
eliminate.push(a);
}
}
while(!eliminate.empty()){
candidates.erase(eliminate.front());
eliminate.pop();
}
/*trav(a,candidates){
//cout<<a<<" "<<i<<" "<<S->query(0,n-1,1,i+1,a-1)<<endl;
if(S->query(0,n-1,1,i+1,a-1)>=arr[a]){
candidates.erase(a);
}
}*/
//candidates.erase(candidates.begin(),candidates.upper_bound(arr[i]));
candidates.insert(i);
}
ST2 *Tree=new ST2();
Tree->build(0,n-1,1);
rep(i,0,n){
Tree->update(0,n-1,1,i,i,arr[i]);
}
//Tree->print(0,n-1,1);
lld answers[q];
for(int i=n-1;i>-1;i--){
trav(a,V[i]){
if(2*a-i<=n-1){
//cout<<i<<" "<<a<<endl;
Tree->update(0,n-1,1,2*a-i,n-1,arr[i]+arr[a]);
//Tree->print(0,n-1,1);
//cout<<endl;
Tree->update(0,n-1,1,2*a-i,n-1,-(arr[i]+arr[a]));
//Tree->print(0,n-1,1);
//cout<<endl;
}
}
trav(a,Queries[i]){
answers[a.second]=Tree->query(0,n-1,1,i,a.first);
}
}
rep(i,0,q){
printf("%lld\n",answers[i]);
}
/*lld ans2=0;
rep(i,0,n){
rep(j,i+1,n){
rep(k,2*j-i,n){
ans2=max(ans2,arr[i]+arr[j]+arr[k]);
}
}
}
rep(i,0,n){
rep(j,i+1,n){
rep(k,2*j-i,n){
if(arr[i]+arr[j]+arr[k]==ans2)cout<<i<<" "<<j<<" "<<k<<endl;
}
}
}
cout<<ans2<<endl;
if(ans!=ans2){
rep(i,0,n)cout<<arr[i]<<" ";
cout<<endl;
}*/
return 0;
}
