#include <bits/stdc++.h>

using namespace std;

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

const int nmax = 2e5;

struct NOD
{
    long long val, total, next, ant;
};

vector <NOD> arb(5 * nmax);
vector <int> a(nmax + 5);

int n, q, start, finish;

NOD compose (NOD st, NOD dr)
{
    NOD r;

    r.total = st.total + dr.total;

    r.val = max (max(st.val, dr.val), st.next + dr.ant);

    r.ant = max(st.ant, st.total + dr.ant);

    r.next = max(dr.next, st.next + dr.total);

    return r;
}

void build (int Nod, int st, int dr)
{
    if (st == dr)
    {
        NOD r;
        r.val = r.ant = r.next = r.total = a[dr];
        arb[Nod] = r;
        return;
    }

    int mij = (st + dr) / 2;

    build(2 * Nod, st, mij);
    build(2 * Nod + 1, mij + 1, dr);

    arb[Nod] = compose(arb[2*Nod], arb[2*Nod+1]);
}

NOD query (int Nod, int st, int dr)
{
    if (start <= st && dr <= finish) return arb[Nod];

    int mij = (st + dr) / 2;

    if (finish <= mij) return query(2 * Nod, st, mij);
    if (mij < start) return query(2 * Nod + 1, mij + 1, dr);

    return compose(query(2 * Nod, st, mij), query(2 * Nod + 1, mij + 1, dr));
}

int main()
{
    fin >> n >> q;
    for (int i=1; i<=n; i++) fin >> a[i];
    build(1, 1, n);
    while(q--)
    {
        fin >> start >> finish;
        fout << query(1, 1, n).val << "\n";
    }
    return 0;
}