#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;typedef long long ll;const ll maxn = 3000100;ll lson[maxn], rson[maxn], lm[maxn], rm[maxn], mans[maxn], sum[maxn];ll ne = 0, root;ll build(ll l, ll r) {    ll now = ++ ne;    if(l ^ r) {        ll mid = (l + r) >> 1;        lson[now] = build(l, mid);        rson[now] = build(mid + 1, r);    }    return now;}void update(ll now) {    if(lson[now]) {        sum[now] = sum[lson[now]] + sum[rson[now]];        lm[now] = max(lm[lson[now]], sum[lson[now]] + lm[rson[now]]);        rm[now] = max(rm[rson[now]], sum[rson[now]] + rm[lson[now]]);        mans[now] = max(max(mans[lson[now]], mans[rson[now]]), lm[rson[now]] + rm[lson[now]]);    }}void insert(ll now, ll l, ll r, ll v, ll pos) {    if(l == r) {        sum[now] = lm[now] = rm[now] = mans[now] = v;    }    else {        ll mid = (l + r) >> 1;        if(pos <= mid) insert(lson[now], l, mid, v, pos);        else insert(rson[now], mid + 1, r, v, pos);        update(now);    }}ll ask(ll now, ll l, ll r, ll ls, ll rs) {    ll ret;    if(l == ls && r == rs) ret = now;    else {        ll mid = (l + r) >> 1;        if(rs <= mid) ret = ask(lson[now], l, mid ,ls, rs);        else if(ls >= mid + 1) ret = ask(rson[now], mid + 1, r, ls, rs);        else {            ret = ++ ne;            ll rl = ask(lson[now], l, mid, ls, mid);            ll rr = ask(rson[now], mid + 1, r, mid + 1, rs);            lson[ret] = rl, rson[ret] = rr;            update(ret);        }    }    return ret;}ll ll_get() {    ll x = 0; char c = (char)getchar(); bool flag = 0;    while(!isdigit(c) && c != ‘-‘) c = (char)getchar();    if(c == ‘-‘) flag = 1;    while(!isdigit(c)) c = (char)getchar();    while(isdigit(c)) {        x = x * 10 + (ll)(c - ‘0‘);        c = (char)getchar();    }    if(flag) x = -x;    return x;}ll n, m;void sov() {    n = ll_get(); root = build(1, n);    for(ll i = 1; i <= n; ++ i) {        ll a = ll_get();        insert(root, 1, n, a, i);    }    m = ll_get();    while(m --) {        ll ls, rs; ls = ll_get(), rs = ll_get();        ll ans = ask(root, 1, n, ls, rs);        printf("%lld\n", mans[ans]);    }}int main() {    //freopen("test.in", "r", stdin);    //freopen("b.out", "w", stdout);    sov();    return 0;}