#include<bits/stdc++.h>
#define N 100010
using namespace std;
typedef long long ll;
struct node{
	ll l,r;
	ll maxn,maxl,maxr,sum;
}t[4*N];
ll n,m,a[50005];
void pushup(ll u){
	t[u].sum=t[u<<1].sum+t[u<<1|1].sum;
    t[u].maxl=max(t[u<<1].maxl,t[u<<1].sum+t[u<<1|1].maxl);
    t[u].maxr=max(t[u<<1|1].maxr,t[u<<1|1].sum+t[u<<1].maxr);
	t[u].maxn=max(max(t[u<<1].maxn,t[u<<1|1].maxn),t[u<<1].maxr+t[u<<1|1].maxl);
}
void build(ll p,ll l,ll r){
	t[p].l=l;t[p].r=r;
	if(l==r){	
	t[p].maxn=a[l];t[p].maxl=a[l];
	t[p].maxr=a[l];t[p].sum=a[l]; 
	return ;
	}
	ll mid=(l+r)>>1;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	pushup(p);
} 
node ask(ll p,ll l,ll r){
	if(t[p].l<=l&&t[p].r>=r){
		return t[p];
	}
	ll mid=(l+r)>>1;
	if(r<=mid) return ask(p<<1,mid+1,t[p].r);
    if(l>mid) return ask(p<<1|1,t[p].l,mid);
	node s ,tl=ask(p<<1,t[p].l,mid ),tr=ask(p<<1|1,mid+1,t[p].r);
	s.sum=tl.sum+tr.sum;
    s.maxl=max(tl.maxl,tl.sum+tr.maxl);
   	s.maxr=max(tr.maxr,tr.sum+tl.maxr);
	s.maxn=max(max(tl.maxn,tr.maxn),tl.maxr+tr.maxl);
	return s;
}
int main(){
	cin >> n ;
	for(ll i=1;i<=n;i++){
		cin >>a[i] ;
	}
	cin >> m ;
	ll x,y;
	build(1,1,n);
	while(m--){
		cin >> x >> y ;
			cout<<ask(1,x,y).maxn<<endl;
	}
	return 0; 
} 

谢谢dalao