#include<fstream>
#include<algorithm>
#include<vector>
#include<string.h>
using namespace std;

ifstream in("sequencequery.in");
ofstream out("sequencequery.out");

struct Node
{
	long long left, right, current, sum;
};

Node arb[200000 * 5 + 30];


void update(int el, int x, int y, long long val, int k)
{
	int mid = (x + y) / 2;

	if (x == y && el == y)
	{
		arb[k].sum = arb[k].left = arb[k].right = arb[k].current = val;
		return;
	}
	else if (el <= mid)
		update(el, x, mid, val, k * 2);
	else
		update(el, mid + 1, y, val, k * 2 + 1);


	arb[k].left = max(arb[k * 2].left, max(arb[k * 2].sum, arb[k * 2].sum + arb[k * 2 + 1].left));
	arb[k].right = max(arb[k * 2 + 1].right, max(arb[k * 2 + 1].sum, arb[k * 2].right + arb[k * 2 + 1].sum));

	arb[k].current = max(arb[k * 2].right + arb[k * 2 + 1].left, max(arb[k * 2].current, arb[k * 2 + 1].current));
	arb[k].sum = arb[k * 2].sum + arb[k * 2 + 1].sum;
}

Node query(int a, int b, int x, int y, int k)
{
	int mid = (x + y) / 2;

	Node e1, e2, p;


	if (x == a && b == y)
		return arb[k];

	if (a <= mid)
	{
		e1 = query(a, min(b, mid), x, mid, k * 2);
		p.left = e1.left;
		p.right = e1.right;
		p.current = e1.current;
		p.sum = e1.sum;
	}

	if (b > mid)
	{
		e2 = query(max(mid + 1, a), b, mid + 1, y, k * 2 + 1);
		p.left = e2.left;
		p.right = e2.right;
		p.current = e2.current;
		p.sum = e2.sum;
	}
	if (a <= mid && b > mid)
	{
		p.left = max(e1.left, max(e1.sum, e1.sum + e2.left));
		p.right = max(e2.right, max(e2.sum, e1.right + e2.sum));

		p.current = max(e1.right + e2.left, max(e1.current, e2.current));
		p.sum = e1.sum + e2.sum;
	}

	return p;
}

int main()
{
	int N, Q;
	in >> N;

	for (int i = 1;i <= N;++i)
	{
		int e;
		in >> e;
		update(i, 1, N, e, 1);
	}
	in >> Q;
	for (int i = 1;i <= Q;++i)
	{
		int a, b;
		in >> a >> b;

		out << query(a + 1, b + 1, 1, N, 1).current << '\n';

	}

	return 0;
}