return ;
}
int m=(l+r)/2;
Bulid(lson,l,m);
Bulid(rson,m+1,r);
Push_Up(step);
}
int Q_L(int step,int l,int r){
if(L[step].left==l&&L[step].right==r)
return L[step].lx;
int m=(L[step].left+L[step].right)/2;
if(r<=m) return Q_L(lson,l,r);
else if(l>m) return Q_L(rson,l,r);
else return max(Q_L(lson,l,m),max(sum[m]-sum[l-1],sum[m]-sum[l-1]+Q_L(rson,m+1,r)));
}
int Q_R(int step,int l,int r){
if(L[step].left==l&&L[step].right==r)
return L[step].rx;
int m=(L[step].left+L[step].right)/2;
if(r<=m) return Q_R(lson,l,r);
else if(l>m) return Q_R(rson,l,r);
else return max(Q_R(rson,m+1,r),max(sum[r]-sum[m],sum[r]-sum[m]+Q_R(lson,l,m)));
int Query(int step,int l,int r){
if(L[step].left==l&&L[step].right==r)
return L[step].mx;
int m=(L[step].left+L[step].right)/2;
if(r<=m) return Query(lson,l,r);
else if(l>m) return Query(rson,l,r);
else return max(max(Query(lson,l,m),Query(rson,m+1,r)),Q_R(lson,l,m)+Q_L(rson,m+1,r));
}
int main(){
while(scanf("%d",&n)!=EOF){
for(int i=1;i<=n;i++) {scanf("%d",&a[i]);sum[i]=sum[i-1]+a[i];}
Bulid(1,1,n);
scanf("%d",&q);
while(q--){
int l,r;
scanf("%d%d",&l,&r);
printf("%d\n",Query(1,l,r));
}
}
return 0;
}