#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

using LL = long long;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;

const int N = 50010;
int lg[N << 2], pos[N << 1], c[N << 1][20], s[N << 1][20];
int w[N], n, m;

void build(int u, int l, int r, int d) {
	if (l == r) {
		pos[l] = u; return;
	}
	int mid = l + (r - l >> 1);
	build(u << 1, l, mid, d + 1);
	build(u << 1 | 1, mid + 1, r, d + 1);
	
	c[mid][d] = w[mid];
	for (int i = mid - 1; i >= l; i -- )
		c[i][d] = max(c[i + 1][d] + w[i], w[i]);
	c[mid + 1][d] = w[mid + 1];
	for (int i = mid + 2; i <= r; i ++ )
		c[i][d] = max(c[i - 1][d] + w[i], w[i]);
	
	s[mid][d] = w[mid];
	for (int i = mid - 1; i >= l; i -- )
		s[i][d] = s[i + 1][d] + w[i];
	s[mid + 1][d] = w[mid + 1];
	for (int i = mid + 2; i <= r; i ++ )
		s[i][d] = s[i - 1][d] + w[i];
	for (int i = mid - 1; i >= l; i -- )
		s[i][d] = max(s[i][d], s[i + 1][d]);
	for (int i = mid + 2; i <= r; i ++ )
		s[i][d] = max(s[i][d], s[i - 1][d]);
}

void init() {
	int Max = 1; while (Max < n) Max <<= 1;
	build(1, 1, Max, 1);
	lg[0] = lg[1] = 1;
	for (int i = 2; i <= Max << 1; i ++ )
		lg[i] = lg[i >> 1] + 1;
}

int query(int l, int r) {
	if (l == r) return w[l];
	int p = lg[pos[r]] - lg[pos[r] ^ pos[l]];
	return max(max(c[l][p], c[r][p]), s[l][p] + s[r][p]);
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i ++ ) {
		scanf("%d", &w[i]);
	}
	
	init();
	
	scanf("%d", &m);
	
	while (m -- ) {
		int l, r;
		scanf("%d%d", &l, &r);
		printf("%d\n", query(l, r));
	}
	
	return 0;
}