#include<bits/stdc++.h>
#define int long long
#define inf 1e18
using namespace std;
int arr[300010];
struct node{
	int arr[4][4];
	node operator*(node b) const{
		node to;
		for(int i=1; i<=3; ++i) {
			for(int j=1; j<=3; ++j) {
				int ans = -inf;
				for(int k=1; k<=3; ++k) {
					ans = max(ans, arr[i][k] + b.arr[k][j]);
				}
				to.arr[i][j] = ans;
			}
		}
		return to;
	}
	void init(int a) {
		arr[1][1] = 0;    arr[1][2] = a;    arr[1][3] = a;
		arr[2][1] = -inf; arr[2][2] = a;    arr[2][3] = a;
		arr[3][1] = -inf; arr[3][2] = -inf; arr[3][3] = 0;
	}
}tree[1000010];
void build(int l, int r, int index) {
	if(l == r) {
		tree[index].init(arr[l]);
		return;
	}
	int mid = l + r >> 1;
	build(l, mid, index*2);
	build(mid+1, r, index*2+1);
	tree[index] = tree[index*2] * tree[index*2+1];
}
node ask(int l, int r, int index, int left, int right) {
	if(r<=right && l>=left) {
		return tree[index];
	}
	node ans; ans.init(-inf);
	if(l>right || r<left) {
		return ans;
	}
	int mid = l + r >> 1;
	ans = ask(l, mid, index*2, left, right) * ask(mid+1, r, index*2+1, left, right);
	return ans;
}
signed main() {
	int n; cin >> n;
	for(int i=1; i<=n; ++i) {
		cin >> arr[i];
	}
	build(1, n, 1);
	int q; cin >> q;
	while(q--) {
		int left, right; cin >> left >> right;
		node temp = ask(1, n, 1, left+1, right);
		cout << max(arr[left]+temp.arr[1][1], max(arr[left]+temp.arr[1][2], temp.arr[1][3])) << endl;
	}
	return 0;
}
/*
100

dp[1] = 1
dp[2] = 3
dp[3] = 5
*/