#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define ll long long
#define MAX 500100
#define  N -20000000000
struct node
{
	ll summa, max_sum, prefix, sufix;
} t[4 * MAX];

void build(ll *a, ll v, ll tl, ll tr)
{
	if (tl == tr) t[v].summa = t[v].max_sum = t[v].prefix = t[v].sufix = a[tl];
	else
	{
		ll tm = (tl + tr) / 2;
		build(a, v * 2, tl, tm);
		build(a, v * 2 + 1, tm + 1, tr);
		t[v].summa = t[v * 2].summa + t[v * 2 + 1].summa;
		t[v].prefix = max(t[v * 2].prefix, t[v * 2].summa + t[v * 2 + 1].prefix);
		t[v].sufix = max(t[v * 2+1].sufix, t[v * 2 + 1].summa + t[v * 2].sufix);
		t[v].max_sum = max(max(t[v * 2].max_sum, t[v * 2 + 1].max_sum), t[v * 2].sufix + t[v * 2 + 1].prefix);
	}
}

ll sum(ll v, ll LeftPos, ll RightPos, ll Left, ll Right)
{
	if (Left > Right) return N;
	if ((Left == LeftPos) && (Right == RightPos)) return t[v].summa;
	ll Middle = (LeftPos + RightPos) / 2;
	return  sum(v * 2, LeftPos, Middle, Left, min(Right, Middle)) +
		sum(v * 2 + 1, Middle + 1, RightPos, max(Left, Middle + 1), Right);
}
ll Pr(ll v, ll LeftPos, ll RightPos, ll Left, ll Right)
{
	if (Left > Right) return N;
	if ((Left == LeftPos) && (Right == RightPos)) return t[v].prefix;
	ll Middle = (LeftPos + RightPos) / 2;
	return max(Pr(v * 2, LeftPos, Middle, Left, min(Right, Middle)),
		sum(v * 2, LeftPos, Middle, Left, min(Right, Middle)) + Pr(v * 2 + 1, Middle + 1, RightPos, max(Left, Middle + 1), Right));
}
ll Sf(ll v, ll LeftPos, ll RightPos, ll Left, ll Right)
{
	if (Left > Right) return N;
	if ((Left == LeftPos) && (Right == RightPos)) return t[v].sufix;
	ll Middle = (LeftPos + RightPos) / 2;
	return max(Sf(v * 2 + 1, Middle + 1, RightPos, max(Left, Middle + 1), Right),
		sum(v * 2 + 1, Middle + 1, RightPos, max(Left, Middle + 1), Right) + Sf(v * 2, LeftPos, Middle, Left, min(Right, Middle)));
}
ll Max(ll v, ll LeftPos, ll RightPos, ll Left, ll Right)
{
	if (Left > Right) return N;
	if ((Left == LeftPos) && (Right == RightPos)) return t[v].max_sum;
	ll Middle = (LeftPos + RightPos) / 2;
	return max(max(Max(v * 2, LeftPos, Middle, Left, min(Right, Middle)) ,
		Max(v * 2 + 1, Middle + 1, RightPos, max(Left, Middle + 1), Right)), Sf(v * 2, LeftPos, Middle, Left, min(Right, Middle)) + Pr(v * 2 + 1, Middle + 1, RightPos, max(Left, Middle + 1), Right));
}


void update(ll v, ll LeftPos, ll RightPos, ll Position, ll NewValue)
{
	if (LeftPos == RightPos) t[v].summa = t[v].max_sum = t[v].prefix = t[v].sufix = NewValue;
	else
	{
		ll Middle = (LeftPos + RightPos) / 2;
		if (Position <= Middle) update(v * 2, LeftPos, Middle, Position, NewValue);
		else update(v * 2 + 1, Middle + 1, RightPos, Position, NewValue);
		t[v].summa = t[v * 2].summa + t[v * 2 + 1].summa;
		t[v].prefix = max(t[v * 2].prefix, t[v * 2].summa + t[v * 2 + 1].prefix);
		t[v].sufix = max(t[v * 2 + 1].sufix, t[v * 2 + 1].summa + t[v * 2].sufix);
		t[v].max_sum = max(max(t[v * 2].max_sum, t[v * 2 + 1].max_sum), t[v * 2].sufix + t[v * 2 + 1].prefix);
	}
}
ll a[500100], n, m, x, y, M;

int main()
{
	scanf("%lld", &n);
	for (ll i = 0; i < n; i++)
	{
		scanf("%lld", &a[i]);
	}
	build(a, 1, 0, n - 1);
	scanf("%lld", &m);
	for (ll i = 0; i < m; i++)
	{
		scanf("%lld", &x);
		scanf("%lld", &y);
		M = Max(1, 0, n-1, x-1, y-1);
		printf("%lld\n", M);
	}
	return 0;
}