#include<bits/stdc++.h>
using namespace std;
const int maxn=50000+10;
int n;
int cnt[maxn];
struct Seg{
	int lmax;
	int rmax;
	int sum;
	int ans;
}tree[3*maxn];
int m;
Seg rs,ls;
void build(int k,int l,int r)
{
	if(l==r)
	{
		tree[k].sum=tree[k].lmax=tree[k].rmax=tree[k].ans=cnt[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	tree[k].sum=tree[k<<1|1].sum+tree[k<<1].sum;
	tree[k].rmax=max(tree[k<<1|1].rmax,tree[k<<1|1].sum+tree[k<<1].rmax);
	tree[k].lmax=max(tree[k<<1].lmax,tree[k<<1].sum+tree[k<<1|1].lmax);
	tree[k].ans=max(tree[k<<1].ans,max(tree[k<<1|1].ans,tree[k<<1].rmax+tree[k<<1|1].lmax));
}
Seg	ask(int k,int l,int r,int x,int y)
{
	int mid=(l+r)>>1;
	if(l<=x&&r>=y) return tree[k];
	if(x>mid) return ask(k<<1|1,mid+1,r,x,y);
	if(y<=mid) return ask(k<<1,l,mid,x,y);
	else{
		Seg ans1;
		rs=ask(k<<1,l,mid,x,y);
		ls=ask(k<<1|1,mid+1,r,x,y);
		ans1.sum=ls.sum+rs.sum;
		ans1.lmax=max(ls.lmax,ls.sum+rs.lmax);
        ans1.rmax=max(rs.rmax,rs.sum+ls.rmax);
		ans1.ans=max(ans1.ans,max(rs.ans,max(ls.ans,ls.rmax+ls.rmax)));
		return ans1;
	}
	
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>cnt[i];
	}
	build(1,1,n);
	cin>>m;
	while(m--)
	{
		int a,b;
		cin>>a>>b;
		cout<<ask(1,1,n,a,b).ans<<endl;
	}
	return 0;
 } 

不知道哪错了，感觉和题解写得一模一样...