#include<bits/stdc++.h>
using namespace std;
#define il inline 
#define L (fa<<1) 
#define R (fa<<1|1) 
#define M ((l+r)>>1) 
const int N=5e4+5;
#define int long long
struct xds{int he,qu,l,r;}xd[N<<3]; 
int a[N],n,m;
il int read(){
	int xxx=0,www=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')www=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')xxx=xxx*10+ch-'0',ch=getchar();
	return xxx*www;}
il xds jia(xds l,xds r){return{l.he+r.he,max(max(l.qu,r.qu),l.r+r.l),max(l.l,l.he+r.l),max(r.r,r.he+l.r)};}
il void pu(int fa){xd[fa]=jia(xd[L],xd[R]);}
il void build(int fa,int l,int r){
	if(l==r){xd[fa]={a[l],a[l],a[l],a[l]};return;}
	build(L,l,M);
	build(R,M+1,r);
	pu(fa);}
il xds he(int nl,int nr,int fa,int l,int r){
	if(nl<=l&&r<=nr)return xd[fa];
	if(nl<=M&&M<nr)return jia(he(nl,nr,L,l,M),he(nl,nr,R,M+1,r));
	if(M<nr)return he(nl,nr,R,M+1,r);//注意能否取等
	if(nl<=M)return he(nl,nr,L,l,M);}
signed main(){
	n=read();
	for(int i=1;i<=n;i++)a[i]=read();
	build(1,1,n);
	m=read();
	while(m--){
		int l=read(),r=read();
		printf("%lld\n",he(l,r,1,1,n).qu);}
    return 0;
}