#include <bits/stdc++.h>
using namespace std;

char *p1, *p2, buf[100000];
#define nc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
inline int rd() 
{
	int x = 0, f = 1; char c = nc();
	while (c < 48 || c > 57) f = (c == '-') ? -1 : 1, c = nc();
	while (c >= 48 && c <= 57) x = x*10 + c-48, c = nc();
	return x*f; 
}

int n, a[50001], m;
struct xdtree 
{
	int l;
	int r;
	int s;
	int xs;
	int lxs;
	int rxs;
} ts[200001];

void init() 
{
//	freopen("GSS1.txt", "r", stdin);
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	cin >> m;
}

void build(int l, int r, int p) 
{
	if (l == r) {
		ts[p] = {l, r, a[l], a[l], a[l], a[l]};
		return;
	}
	int mid = l + ((r - l) >> 1);
	build(l, mid, 2*p);
	build(mid+1, r, 2*p+1);
	ts[p] = {
		l, r, 
		ts[2*p].s + ts[2*p+1].s, 
		max(max(ts[2*p].xs, ts[2*p+1].xs), ts[2*p].rxs+ts[2*p+1].lxs), 
		max(ts[2*p].lxs, ts[2*p].s+ts[2*p+1].lxs), 
		max(ts[2*p].rxs+ts[2*p+1].s, ts[2*p+1].rxs)
	};
}

xdtree query(int ls, int rs, int p) 
{
	int l = ts[p].l, r = ts[p].r, mid = l + ((r - l) >> 1);
	if (l >= ls && r <= rs) return ts[p];
	if (ls > mid) return query(ls, rs, 2*p+1);
	if (rs <= mid) return query(ls, rs, 2*p);
	xdtree a = query(ls, mid, 2*p), b = query(mid+1, rs, 2*p+1);
	return {
		ls, rs, 
		a.s + b.s, 
		max(max(a.xs, b.xs), a.rxs+b.lxs), 
		max(a.lxs, a.s+b.lxs), 
		max(a.rxs+b.s, b.rxs)
	};
}

void search() 
{
	int ls, rs;
	for ( ; m; --m) {
		cin >> ls >> rs;
		cout << query(ls, rs, 1).xs << endl;
	}
}

int main() 
{
	init();
	build(1, n, 1);
	search();
	return 0;
}