#include <iostream>
#include <stdio.h>

using namespace std;
typedef long long ll;

struct Node {
	ll left;
	ll right;
	ll sum;
	ll best;
};

int a[100000];
Node tree[1000000];

int max(int n1, int n2)
{
	if (n1 > n2)return n1;
	return n2;
}


void build_tree(int node, int start, int endd)
{
	if (start == endd) {
		tree[node].right = tree[node].left = tree[node].best = tree[node].sum = a[start];
		return;
	}
	int mid = (start + endd) / 2;
	build_tree(node * 2, start, mid);
	build_tree((node * 2) + 1, mid + 1, endd);
	tree[node].left = max(tree[node * 2].left, tree[node * 2].sum + tree[(node * 2) + 1].left);
	tree[node].right = max(tree[(node * 2) + 1].right, tree[(node * 2) + 1].sum + tree[node * 2].right);
	tree[node].best = max(tree[node * 2].right + tree[(node * 2) + 1].left, max(tree[node * 2].best, tree[(node * 2) + 1].best));
	tree[node].sum = tree[node * 2].sum + tree[(node * 2) + 1].sum;
	return;
}

ll quary(int node, int start, int endd, int l, int r)
{
	if (start > r || endd < l)return -1000000;
	if (start >= l && endd <= r)return tree[node].best;
	int mid = (start + endd) / 2;
	return max(max(quary(node * 2, start, mid, l, r), quary((node * 2) + 1, mid + 1, endd, l, r)), quary(node * 2, start, mid, l, r) + quary((node * 2) + 1, mid + 1, endd, l, r));
}

int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	build_tree(1, 1, n);
	int m, l, r;
	scanf("%d", &m);
	while (m--) {
		scanf("%d %d",&l,&r);
		if (l > r)
			swap(l, r);
		ll ans = quary(1, 1, n , l, r);
		printf("%lld\n", ans);
	}
	return 0;
}