#include<bits/stdc++.h>
using namespace std;
struct node{
	int lmax,rmax;
	int l,r;
	int max;
	int sum;
};
node T[200005];
int n,m;
int a[100005];
void push_up(int p){
	T[p].sum=T[p*2].sum+T[p*2+1].sum;
	T[p].lmax=max(T[p*2].lmax,T[p*2].sum+T[p*2+1].lmax);
	T[p].rmax=max(T[p*2+1].rmax,T[p*2+1].sum+T[p*2].rmax);
	T[p].max=max(T[p*2].max,max(T[p*2+1].max,T[p*2].rmax+T[p*2+1].lmax));
}
void build(int l,int r,int p){
	T[p].l=l,T[p].r=r;
	if(l==r){
		T[p].sum=T[p].lmax=T[p].rmax=T[p].max=a[l];
		return ;
	}
	int mid=(l+r)/2;
	build(l,mid,p*2);
	build(mid+1,r,p*2+1);
	push_up(p);
}
node query(int a,int b,int l,int r,int p){
	if(a<=T[p].l&&b>=T[p].r){
		return T[p];
	}
	int mid=(T[p].l+T[p].r)/2;
	if(a<=mid){
		return query(a,b,l,mid,p*2);
	}
	if(b>mid){
		return query(a,b,mid+1,r,p*2+1);
	}
	else{
		node left,right;
		left=query(a,b,l,mid,p*2),right=query(a,b,mid+1,r,p*2+1);
		node ans;
		ans.sum=left.sum+right.sum;
		ans.max=max(max(left.max,left.rmax+right.lmax),right.max);
		ans.lmax=max(left.lmax,left.sum+right.lmax);
		ans.rmax=max(right.rmax,right.sum+left.rmax);
		return ans;
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	build(1,n,1);
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		printf("%d\n",query(a,b,1,n,1).max);
	}
	return 0;
}


//SP1043 GSS1 - Can you answer these queries I

SPOJ上面好像是RE，但洛谷显示的是WA（用的自己的账户）