#include <bits/stdc++.h>

using namespace std;

ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
struct Nod {
    int sum, pref, suf, rasp;
} a[400002];
int n, m;

static inline Nod Calc(Nod a, Nod b) {
    return {
        a.sum + b.sum,
        max(a.pref, a.sum + b.pref),
        max(b.suf,  b.sum + a.suf),
        max({a.rasp, b.rasp, a.suf + b.pref}),
    };
}

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

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

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

/*static inline void Update(int st, int dr, int poz, int val, int nod = 1) {
    if(st == dr) {
        a[nod].sum  = val;
        a[nod].pref = val;
        a[nod].suf  = val;
        a[nod].rasp = val;
    }
    else {
        int mij = st + (dr - st) / 2;

        if(poz <= mij) Update(st     , mij, poz, val, 2 * nod);
        if(mij <  poz) Update(mij + 1, dr , poz, val, 2 * nod + 1);

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

static inline Nod Query(int st, int dr, int pst, int pdr, int nod = 1) {
    if(pst <= st && dr <= pdr) return a[nod];
    else {
        int mij = st + (dr - st) / 2;

        Nod q1 = {0, 0, 0, 0};
        Nod q2 = {0, 0, 0, 0};

        if(poz <= mij) q1 = Query(st     , mij, poz, val, 2 * nod);
        if(mij <  poz) q2 = Query(mij + 1, dr , poz, val, 2 * nod + 1);

        return Calc(q1, q2);
    }
}

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

    while(m--) {
        int st, dr;
        fin >> st >> dr;
        fout << Query(1, n, st, dr).rasp << "\n";
    }

	return 0;
}