#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct segtree{
	ll s, bs, bps, bss;
}st[200020];
ll a[50005];
segtree merge(segtree A, segtree B)
{
	segtree C;
	C.s=A.s+B.s;
	C.bps=max(A.bps, A.s+B.bps);
	C.bss=max(B.bss, B.s+A.bss);
	C.bs=max(max(B.s, A.s), A.bss+B.bps);
	return C;
}
void build(ll start, ll end, ll node)
{
	if(start==end)
	{
		st[node].s=st[node].bps=st[node].bss=st[node].bs=a[start];
		return ;
	}
	ll mid=(start+end)/2;
	build(start, mid, 2*node);
	build(mid+1, end, 2*node+1);
	st[node]=merge(st[2*node], st[2*node+1]);
}
segtree query(ll start, ll end, ll l, ll r, ll node)
{
	if(start>=l&&end<=r) return st[node];
	ll mid=(start+end)/2;
	if(mid>=r) return query(start, mid, l, r, 2*node);
	else if(mid<l) return query(mid+1, end, l, r, 2*node+1);
	else
	return merge(query(start, mid, l, r, 2*node), query(mid+1, end, l,r, 2*node+1));
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll n;
	cin>>n;
	for(ll i=1;i<=n;i++)
	cin>>a[i];
	build(1, n, 1);
	ll q;
	cin>>q;
	while(q--)
	{
		ll x, y;
		cin>>x>>y;
		segtree ss=query(1, n, x, y, 1);
		cout<<ss.bs<<endl;
	}
}