#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10;
inline int read(){
    int x=0;
    bool f=true;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()){
        if(ch=='-')f=false;
    }
    for(;isdigit(ch);ch=getchar())
        x=(x<<1)+(x<<3)+ch-'0';
    return f?x:~(x-1);
}
int n,num[N];
struct node{
    int l,r,maxsum,maxl,maxr,sum;
}a[N<<2];
void update(int k){
    a[k].sum=a[k<<1].sum+a[k<<1|1].sum;
    a[k].maxl=max(a[k<<1].maxl,a[k<<1].sum+a[k<<1|1].maxl);
    a[k].maxr=max(a[k<<1|1].maxr,a[k<<1|1].sum+a[k<<1].maxr);
    a[k].maxsum=max(a[k<<1].maxsum,max(a[k<<1|1].maxsum,a[k<<1].maxr+a[k<<1|1].maxl));
}
void build(int k,int l,int r){
    if(l==r){
        a[k].sum=num[l];
        a[k].maxsum=num[l];
        a[k].maxl=num[l];
        a[k].maxr=num[l];
        return;
    }
    int mid=(l+r)>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    update(k);
}
node segmentsum(int k,int x,int y,int l,int r){
    if(x<=l&&y>=r){
        return a[k];
    }
    int mid=(l+r)>>1;
    if(y<=mid)return segmentsum(k<<1,x,y,l,mid);
    if(x>mid)return segmentsum(k<<1|1,x,y,mid+1,r);
    node ans,a,b;
    a=segmentsum(k<<1,x,y,l,mid);
    b=segmentsum(k<<1|1,x,y,mid+1,r);
    ans.sum=a.sum+b.sum;
    ans.maxl=max(a.maxl,a.sum+b.maxl);
    ans.maxr=max(b.maxr,b.sum+a.maxr);
    ans.maxsum=max(a.maxsum,max(b.maxsum,a.maxr+b.maxl));
    return ans;
}
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        num[i]=read();
    }
    build(1,1,n);
    int T=read();
    while(T--){
        int x=read(),y=read();
        printf("%d\n",segmentsum(1,x,y,1,n).maxsum);
    }
    system("pause");
    return 0;
}