#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector <int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> ii;
#define pb push_back
#define INF 100000000
#define mp make_pair
#define MOD 1000000007
#define F first
#define S second
int n;
ll a[100005];
ll total[200005];
ll ans[200005];
ll pref[200005];
ll suff[200005];
int main() {
ios::sync_with_stdio(false);
cin >> n;
int x = 1;
while (x < n) x *= 2;
for (int i = 0; i < n; i ++) cin >> a[i];
for (int i = n; i < x; i++) a[i] = -(INF*INF);
n = x;
for (int i = n; i < 2*n; i++) total[i] = a[i-n];
for (int i = n-1; i > 0; i--) total[i] = total[i*2]+total[i*2+1];
for (int i = n; i < 2*n; i++) pref[i] = a[i-n];
for (int i = n-1; i > 0; i--) pref[i] = max(pref[i*2],total[i*2]+pref[i*2+1]);
for (int i = n; i < 2*n; i++) suff[i] = a[i-n];
for (int i = n-1; i > 0; i--) suff[i] = max(suff[i*2+1],total[i*2+1]+suff[i*2]);
for (int i = n; i < 2*n; i++) ans[i] = a[i-n];
for (int i = n-1; i > 0; i--) ans[i] = max(suff[i*2]+pref[i*2+1],
max(ans[i*2],ans[i*2+1])
);
// for (int i = 0; i < 2*n; i++) cout << i << " - " << ans[i] << endl;
int m;
cin >> m;
while (m --){
int l,r;
cin >> l >> r;
l --;
l += n;
r += n;
ll res = -1500000;
while (l < r){
if (l%2) res = max(res,ans[l++]);
if (r%2) res = max(res,ans[--r]);
l /= 2;
r /= 2;
}
cout << res << endl;
}
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp0eXBlZGVmIGxvbmcgbG9uZyBsbDsKdHlwZWRlZiB2ZWN0b3IgPGludD4gdmk7CnR5cGVkZWYgdmVjdG9yPHZpPiB2dmk7CnR5cGVkZWYgcGFpcjxpbnQsaW50PiBpaTsKI2RlZmluZSBwYiBwdXNoX2JhY2sKI2RlZmluZSBJTkYgMTAwMDAwMDAwCiNkZWZpbmUgbXAgbWFrZV9wYWlyCiNkZWZpbmUgTU9EIDEwMDAwMDAwMDcKI2RlZmluZSBGIGZpcnN0CiNkZWZpbmUgUyBzZWNvbmQKCmludCBuOwpsbCBhWzEwMDAwNV07CmxsIHRvdGFsWzIwMDAwNV07CmxsIGFuc1syMDAwMDVdOwpsbCBwcmVmWzIwMDAwNV07CmxsIHN1ZmZbMjAwMDA1XTsKCmludCBtYWluKCkgewoJCglpb3M6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CiAgICBjaW4gPj4gbjsKICAgIGludCB4ID0gMTsKICAgIHdoaWxlICh4IDwgbikgeCAqPSAyOwogICAgCiAgICBmb3IgKGludCBpID0gMDsgaSA8IG47IGkgKyspIGNpbiA+PiBhW2ldOwogICAgZm9yIChpbnQgaSA9IG47IGkgPCB4OyBpKyspIGFbaV0gPSAtKElORipJTkYpOwogICAgCiAgICBuID0geDsKICAgIAogICAgZm9yIChpbnQgaSA9IG47IGkgPCAyKm47IGkrKykgdG90YWxbaV0gPSBhW2ktbl07CiAgICBmb3IgKGludCBpID0gbi0xOyBpID4gMDsgaS0tKSB0b3RhbFtpXSA9IHRvdGFsW2kqMl0rdG90YWxbaSoyKzFdOwogICAgCiAgICBmb3IgKGludCBpID0gbjsgaSA8IDIqbjsgaSsrKSBwcmVmW2ldID0gYVtpLW5dOwogICAgZm9yIChpbnQgaSA9IG4tMTsgaSA+IDA7IGktLSkgcHJlZltpXSA9IG1heChwcmVmW2kqMl0sdG90YWxbaSoyXStwcmVmW2kqMisxXSk7CiAgICAKICAgIGZvciAoaW50IGkgPSBuOyBpIDwgMipuOyBpKyspIHN1ZmZbaV0gPSBhW2ktbl07CiAgICBmb3IgKGludCBpID0gbi0xOyBpID4gMDsgaS0tKSBzdWZmW2ldID0gbWF4KHN1ZmZbaSoyKzFdLHRvdGFsW2kqMisxXStzdWZmW2kqMl0pOwogICAgCiAgICBmb3IgKGludCBpID0gbjsgaSA8IDIqbjsgaSsrKSBhbnNbaV0gPSBhW2ktbl07CiAgICBmb3IgKGludCBpID0gbi0xOyBpID4gMDsgaS0tKSBhbnNbaV0gPSBtYXgoc3VmZltpKjJdK3ByZWZbaSoyKzFdLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIG1heChhbnNbaSoyXSxhbnNbaSoyKzFdKQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICk7CiAgICAKICAgIC8vIGZvciAoaW50IGkgPSAwOyBpIDwgMipuOyBpKyspIGNvdXQgPDwgaSA8PCAiIC0gIiA8PCBhbnNbaV0gPDwgZW5kbDsKICAgIAogICAgaW50IG07CiAgICBjaW4gPj4gbTsKICAgIHdoaWxlIChtIC0tKXsKICAgICAgICBpbnQgbCxyOwogICAgICAgIGNpbiA+PiBsID4+IHI7CiAgICAgICAgbCAtLTsKICAgICAgICBsICs9IG47CiAgICAgICAgciArPSBuOwogICAgICAgIGxsIHJlcyA9IC0xNTAwMDAwOwogICAgICAgIHdoaWxlIChsIDwgcil7CiAgICAgICAgICAgIGlmIChsJTIpIHJlcyA9IG1heChyZXMsYW5zW2wrK10pOwogICAgICAgICAgICBpZiAociUyKSByZXMgPSBtYXgocmVzLGFuc1stLXJdKTsKICAgICAgICAgICAgbCAvPSAyOwogICAgICAgICAgICByIC89IDI7CiAgICAgICAgfQogICAgICAgIGNvdXQgPDwgcmVzIDw8IGVuZGw7CiAgICB9Cn0=