#include<bits/stdc++.h>
#define INF 11124455
using namespace std;
constexpr int N=5e4+10;
struct SegmentTree{
	int l,r;
	int sum,data,pre,suf;
	SegmentTree(){
		l=r=0;
		sum=0;
		data=pre=suf=-INF;
	}
	#define l(x) tree[x].l
	#define r(x) tree[x].r
	#define sum(x) tree[x].sum
	#define data(x) tree[x].data
	#define pre(x) tree[x].pre
	#define suf(x) tree[x].suf
};SegmentTree tree[N<<2];
int n,m;
int a[N];
void build(int p,int l,int r){
	l(p)=l,r(p)=r;
	if(l==r){
		sum(p)=data(p)=pre(p)=suf(p)=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	sum(p)=sum(p<<1)+sum(p<<1|1);
	data(p)=max(max(data(p<<1),data(p<<1|1)),suf(p<<1)+pre(p<<1|1));
	pre(p)=max(pre(p<<1),sum(p<<1)+pre(p<<1|1));
	suf(p)=max(suf(p<<1|1),sum(p<<1|1)+suf(p<<1));
	return ;
}
int query(int p,int l,int r){
	if(l<=l(p) && r>=r(p)){
		return data(p);
	}
	int mid=(l(p)+r(p))>>1;
	int res=0;
	if(l<=mid){
		res+=query(p<<1,l,r);
	}
	if(r>mid){
		res+=query(p<<1|1,l,r);
	}
	return res;
}
int main(){
	#define false 0
	ios::sync_with_stdio(false);
	cin.tie(false),cout.tie(false);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,1,n);
	cin>>m;
	while(m--){
		int l,r;
		cin>>l>>r;
		cout<<query(1,l,r)<<"\n";
	}
	return 0;
}