#include<bits/stdc++.h>
//#define int long long 
using namespace std;
const int N=50001,INF=0x3f3f3f3f;
int n,m,cur=1,tot,a[N];
struct SegmentTreeNode{
    int l,r,ff,lf,g,ls,rs,f;
    SegmentTreeNode(){
        l=r=g=ls=rs=lf=ff=f=0;
    }
    SegmentTreeNode(int k){
    	l=r=k,ff=lf=g=f=a[k];
	}
    friend SegmentTreeNode operator+(SegmentTreeNode a,SegmentTreeNode b){
        SegmentTreeNode c;
        c.l=min(a.l,b.l),c.r=max(a.r,b.r);
        c.g=a.g+b.g,c.f=max({a.f,b.f,a.lf+b.ff});
        c.ff=max(a.ff,a.g+b.ff),c.lf=max(b.lf,b.g+a.lf);
        return c;
    }
    SegmentTreeNode operator+=(SegmentTreeNode b){
        (*this)=(*this)+b;
        return*this;
    }
}s[N<<1];
void pushup(int x){
    s[x]=s[s[x].ls]+s[s[x].rs];
	return;
}
void build(int l,int r,int&cur){
	cur=++tot;
	if(l==r){
        s[cur]=SegmentTreeNode(l);
		return;
	}
	int mid=l+r>>1; 
	return build(l,mid,s[cur].ls),build(mid+1,r,s[cur].rs),pushup(cur);
}
SegmentTreeNode qry(int ql,int qr,int cur){
	int l=s[cur].l,r=s[cur].r;
	if(ql<=l&&r<=qr)
		return s[cur];
	int mid=l+r>>1;
	SegmentTreeNode ans;
	if(ql<=mid)
		ans+=qry(ql,qr,s[cur].ls);
	if(mid<qr)
		ans+=qry(ql,qr,s[cur].rs);
	return ans;
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++)
    	cin>>a[i];
    build(1,n,cur);
    cin>>m;
    while(m--){
        int l,r;
        cin>>l>>r;
        cout<<qry(l,r,1).f<<'\n';
	}
    return 0;
}#include<bits/stdc++.h>
//#define int long long 
using namespace std;
const int N=50001,INF=0x3f3f3f3f;
int n,m,cur=1,tot,a[N];
struct SegmentTreeNode{
    int l,r,ff,lf,g,ls,rs,f;
    SegmentTreeNode(){
        l=r=g=ls=rs=lf=ff=f=0;
    }
    SegmentTreeNode(int k){
    	l=r=k,ff=lf=g=f=a[k];
	}
    friend SegmentTreeNode operator+(SegmentTreeNode a,SegmentTreeNode b){
        SegmentTreeNode c;
        c.l=min(a.l,b.l),c.r=max(a.r,b.r);
        c.g=a.g+b.g,c.f=max({a.f,b.f,a.lf+b.ff});
        c.ff=max(a.ff,a.g+b.ff),c.lf=max(b.lf,b.g+a.lf);
        return c;
    }
    SegmentTreeNode operator+=(SegmentTreeNode b){
        (*this)=(*this)+b;
        return*this;
    }
}s[N<<1];
void pushup(int x){
    s[x]=s[s[x].ls]+s[s[x].rs];
	return;
}
void build(int l,int r,int&cur){
	cur=++tot;
	if(l==r){
        s[cur]=SegmentTreeNode(l);
		return;
	}
	int mid=l+r>>1; 
	return build(l,mid,s[cur].ls),build(mid+1,r,s[cur].rs),pushup(cur);
}
SegmentTreeNode qry(int ql,int qr,int cur){
	int l=s[cur].l,r=s[cur].r;
	if(ql<=l&&r<=qr)
		return s[cur];
	int mid=l+r>>1;
	SegmentTreeNode ans;
	if(ql<=mid)
		ans+=qry(ql,qr,s[cur].ls);
	if(mid<qr)
		ans+=qry(ql,qr,s[cur].rs);
	return ans;
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++)
    	cin>>a[i];
    build(1,n,cur);
    cin>>m;
    while(m--){
        int l,r;
        cin>>l>>r;
        cout<<qry(l,r,1).f<<'\n';
	}
    return 0;
}