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

const int Maxn=3e5+7,Mod=998244353;
int n,Q,a[Maxn];
int Log[Maxn];

namespace DS{
	int t[Maxn*20],g[Maxn*20],lim=1,len;
	inline void Init(int n){
		while(lim<=n) lim<<=1,len++;
		for(int dep=0;dep<len;dep++){
			int *s=t+(dep<<len),*q=g+(dep<<len);
			for(int i=0;i<lim;i+=(1<<(len-dep))){
				int l=i,r=l+(1<<(len-dep))-1,mid=l+(1<<(len-dep-1));
				int suf=a[mid-1],pre=max(suf,0);
				s[mid-1]=suf,q[mid-1]=suf;
				for(int k=mid-2;k>=l;k--) suf+=a[k],pre+=a[k],s[k]=max(s[k+1],suf),q[k]=max(q[k+1],pre),pre=max(pre,0);
				suf=a[mid],pre=max(suf,0);
				s[mid]=suf,q[mid]=suf;
				for(int k=mid+1;k<=r;k++) suf+=a[k],pre+=a[k],s[k]=max(s[k-1],pre),q[k]=max(q[k-1],pre),pre=max(pre,0);
			}
		}
	}
	inline int query(int l,int r){
		if(l>r) return 0;
		if(l==r) return a[l];
		int d=len-Log[l^r]-1;
		return max(t[d<<len|l]+t[d<<len|r],max(g[d<<len|l],g[d<<len|r]));
	}		
};

int main(){
	scanf("%d",&n);
	for(int i=2;i<Maxn;i++) Log[i]=Log[i>>1]+1;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	DS::Init(n);
	scanf("%d",&Q);
	while(Q--){
		int l,r;
		scanf("%d%d",&l,&r);
		printf("%d\n",DS::query(l,r));
	}
	return 0;
}

/*
3 
-1 2 -3
1
1 3

12
-1 3 -4 2 4 -1 3 5 -1 4 -7 9
9
1 2
2 5
7 12
6 12
5 12
3 5 
2 4
3 8
1 1

*/