#include<bits/stdc++.h>
#define int long long
using namespace std;

const int maxn=5e5+10;
int n,q;
int a[maxn];
struct Node{
	int l,r;
	int tot;
	int pre;
	int suf;
	int mx;
	Node(){l=r=tot=pre=suf=mx=0;}
	Node operator +(const Node& nx)const{
		Node p;
		p.l=l;
		p.r=nx.r;
		p.tot=tot+nx.tot;
		p.pre=max(pre,tot+nx.pre);
		p.suf=max(suf,nx.tot+suf);
		p.mx=max(mx,nx.mx);
		p.mx=max(p.mx,suf+nx.pre);
		return p;
	}
}t[maxn<<2];
inline void upd(int i){t[i]=t[i<<1]+t[(i<<1)|1];}
//inline void upd(int i){t[i]=t[i<<1|1]+t[i<<1];}
inline void build(int i,int l,int r){
	t[i].l=l;
	t[i].r=r;
	if(l==r){
		t[i].mx=a[l];
		t[i].tot=a[l];
		t[i].pre=a[l];
		t[i].suf=a[l];
		return ;
	}
	int mid=l+r>>1;
	build(i<<1,l,mid);
	build((i<<1)|1,mid+1,r);
	upd(i);
}
Node query(int i,int l,int r){
	//printf("IAKIOI\n");
	//if(l>t[i].r||t[i].r<l)return s;
	if(t[i].l>=l&&t[i].r<=r)return t[i];
	int mid=t[i].l+t[i].r>>1;
	if(r>mid&&l<=mid)return query(i<<1,l,r) + query((i<<1)|1,l,r);
//	if(r>mid&&l<=mid)return query(i<<1|1,l,r) + query(i<<1,l,r);
	else{
		if(l<=mid)return query(i<<1,l,r);
		if(r>mid)return query((i<<1)|1,l,r);
	}
}
signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
	build(1,1,n);
	scanf("%lld",&q);
	//printf("%d %d %d %d %d %d \n",s.l,s.r,s.tot,s.mx,s.pre,s.suf);
	while(q--){
		int lt,rt;
		scanf("%lld%lld",&lt,&rt);
		Node ans=query(1,lt,rt);
		printf("%lld\n",ans.mx);
	}
	return 0;
}