#include <bits/stdc++.h>

using namespace std;

ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
struct Nod {
    long long sum, secv, pref, suf;
} v[400002];
long long n, i, t, qx, qy;

static inline Nod Calc(Nod a, Nod b) {
    Nod c;
    c.sum = a.sum + b.sum;
    c.pref = max(a.pref, a.sum + b.pref);
    c.suf = max(b.suf, a.suf + b.sum);
    c.secv = max(a.suf + b.pref, max(a.secv, b.secv));

    return c;
}

static inline void Build(int nod, int st, int dr) {
    if(st == dr) {
        fin >> v[nod].sum;
        v[nod].pref = v[nod].sum;
        v[nod].suf = v[nod].sum;
        v[nod].secv = v[nod].sum;
    }
    else {
        int mij = st + (dr - st) / 2;

        Build(2 * nod    , st     , mij);
        Build(2 * nod + 1, mij + 1, dr );

        v[nod] = Calc(v[2 * nod], v[2 * nod + 1]);
    }
}

static inline Nod Query(int nod, int st, int dr, const int qx, const int qy) {
    if(qx <= st && dr <= qy) return v[nod];
    else {
        int mij = st + (dr - st) / 2;

        if(qy <= mij) return Query(2 * nod    , st     , mij, qx, qy);
        if(mij <  qx) return Query(2 * nod + 1, mij + 1, dr , qx, qy);
        return          Calc(Query(2 * nod    , st     , mij, qx, qy),
                             Query(2 * nod + 1, mij + 1, dr , qx, qy));
    }
}

int main() {
    fin >> n >> t;
    Build(1, 1, n);

    while(t--) {
        fin >> qx >> qy;
        fout << Query(1, 1, n, qx, qy).secv << "\n";
    }

    return 0;
}