#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define int long long
#define ls(x) x<<1
#define rs(x) x<<1|1 
using namespace std;
const int N=1e5+10;
typedef pair<int,int> PII;
int n,m,a[N];
struct tree
{
	int l,r;
	int sum,ans,pre,suc;
}t[N<<2];
void pushup(int p)
{
	t[p].sum=t[ls(p)].suc+t[rs(p)].sum;
	t[p].ans=max(max(t[ls(p)].ans,t[rs(p)].ans),t[ls(p)].suc+t[rs(p)].pre);
	t[p].pre=max(t[ls(p)].pre,t[ls(p)].sum+t[rs(p)].pre);
	t[p].suc=max(t[rs(p)].suc,t[rs(p)].sum+t[ls(p)].suc);	
}
void build(int p,int l,int r)
{
	t[p].l=l,t[p].r=r;
	if(l==r) 
	{
		t[p].sum=t[p].suc=t[p].pre=t[p].ans=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(ls(p),l,mid),build(rs(p),mid+1,r);
	pushup(p);
}
queue<int> q;
void query(int p,int l,int r)
{
	if(l<=t[p].l&&t[p].r<=r)
	{
		q.push(p);
//		cout<<p<<' '<<t[p].l<<' '<<t[p].r<<endl;
		return;
	}
	int mid=(t[p].l+t[p].r)>>1;
	if(l<=mid) query(ls(p),l,r);
	if(r>mid) query(rs(p),l,r);
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	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;
		query(1,l,r);
		int res=t[q.front()].ans,res1=t[q.front()].suc;
		q.pop();
		while(!q.empty())
		{
			int x=q.front();
//			cout<<res<<' '<<res1<<endl;
			res=max(max(res,t[x].ans),res1+t[x].pre);
			res1=max(res1+t[x].sum,t[x].suc);
			q.pop();
		}
		cout<<res<<'\n';
	}
	return 0;
}