#include <iostream>
#include <fstream>

using namespace std;

ifstream in ("sequencequery.in");
ofstream out ("sequencequery.out");

template <class T1, class T2>
inline long long max (const T1 &A, const T2 &B)
{
    if (A > B)
        return A;

    return B;
}

struct nod
{
    long long sum;
    long long pref, suf;
    long long best;

    nod ()
    {
        upd (-(1LL << 60));
    }

    void upd (const long long &val)
    {
        sum = val;
        pref = val;
        suf = val;
        best = val;
    }

    void update (const nod &st, const nod &dr)
    {
        sum = st.sum + dr.sum;
        pref = max (st.pref, st.sum + dr.pref);
        suf = max (dr.suf, dr.sum + st.suf);
        best = max (st.best, dr.best);
        best = max (best, st.suf + dr.pref);
    }
};

nod AINT[1 << 19];
long long Ans, S = 0;

void update (int nod, int st, int dr, int poz, int val)
{
    if (st == dr){
        AINT[nod].upd (val);

        return;
    }

    int mid = (st + dr) >> 1;

    if (poz <= mid)
        update (nod << 1, st, mid, poz, val);
    else
        update (nod << 1 | 1, mid + 1, dr, poz, val);

    AINT[nod].update (AINT[nod << 1], AINT[nod << 1 | 1]);
}

void query (int nod, int st, int dr, int a, int b)
{
    int mid = (st + dr) >> 1;
    long long now;

    if (a <= st && dr <= b){
        now = max (S + AINT[nod].pref, AINT[nod].best);
        Ans = max (Ans, now);
        S = max (S + AINT[nod].sum, AINT[nod].suf);
    }
    else{
        if (a <= mid)
            query (nod << 1, st, mid, a, b);
        if (b > mid)
            query (nod << 1 | 1, mid + 1, dr, a, b);
    }
}

int main()
{
    int N, M, i, a, b, tip;

    in >> N;

    for (i = 1; i <= N; i ++){
        in >> a;

        update (1, 1, N, i, a);
    }

    in >> M;

    while (M --){
        in >> a >> b;

        Ans = -(1LL << 60);
        S = 0;
        query (1, 1, N, a, b);
        out << Ans << "\n";
    }

    return 0;
}