#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const int N=5e4+10;
int a[N];
#define lc u<<1
#define rc ((u<<1)|1)
struct Tree{
    int pre,suf,sum,maxn;
}tr[N*4];
#define mid ((l+r)>>1)
int n,m;
void pushup(int u){
    tr[u].sum=tr[lc].sum+tr[rc].sum;
    tr[u].pre=max(tr[lc].pre,tr[lc].sum+tr[rc].pre);
    tr[u].suf=max(tr[rc].suf,tr[rc].sum+tr[lc].suf);
    tr[u].maxn=max(tr[rc].maxn,tr[lc].maxn);
    tr[u].maxn=max(tr[rc].maxn,tr[lc].suf+tr[rc].pre);
}
void build(int u,int l,int r){
    if(l==r){
        tr[u].suf=tr[u].sum=tr[u].maxn=tr[u].pre=a[l];
        return;
    }
    build(lc,l,mid);
    build(rc,mid+1,r);
    pushup(u);
}
Tree query(int u,int l,int r,int x,int y){
    if(x<=l&&r<=y){
        return tr[u];
    }
    if(y<=mid) return query(lc,l,mid,x,y);
    if(x>mid) return query(rc,mid+1,r,x,y);
    else{
        Tree ans,a,b;
        a=query(lc,l,mid,x,y),b=query(rc,mid+1,r,x,y);
        ans.sum=a.sum+b.sum;
        ans.pre=max(a.pre,a.sum+b.pre);
        ans.suf=max(b.suf,b.sum+a.suf);
        ans.maxn=max(b.maxn,a.maxn);
        ans.maxn=max(b.maxn,a.suf+b.pre);
        return ans;
    } 
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i) cin>>a[i];
    build(1,1,n);
    cin>>m;
    for(int i=1;i<=m;++i){
        int l,r;cin>>l>>r;
        cout<<query(1,1,n,l,r).maxn<<endl;
    }
    return 0;
}