#include <fstream>
using namespace std;

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

struct el
{
    long long smax, prefmax, sufmax, stot;
} a[400001];

el comb (el a, el b)
{
    el c;

    c.smax = max (a.smax, b.smax);
    c.smax = max (c.smax, a.sufmax + b.prefmax);
    c.prefmax = max (a.prefmax, a.stot + b.prefmax);
    c.sufmax = max (b.sufmax, b.stot + a.sufmax);
    c.stot = a.stot + b.stot;

    return c;
}

void constr (int nod, int st, int dr)
{
    if (st == dr)
    {
        int x;
        fin >> x;
        a[nod] = {x, x, x, x};
    }
    else
    {
        int mij = (st+dr)>>1;
        constr (nod<<1, st, mij);
        constr (nod<<1|1, mij+1, dr);

        a[nod] = comb (a[nod<<1], a[nod<<1|1]);
    }
}

el query (int nod, int st, int dr, int qst, int qdr)
{
    if (qst <= st && dr <= qdr)
        return a[nod];

    int mij = (st+dr)>>1;
    el eins, zwei;
    eins = zwei = {-1ll<<50, -1ll<<50, -1ll<<50, 0};

    if (qst <= mij)
        eins = query (nod<<1, st, mij, qst, qdr);
    if (mij < qdr)
        zwei = query (nod<<1|1, mij+1, dr, qst, qdr);

    return comb (eins, zwei);
}

int main()
{
    //nu uita de initializarea lui a!
    int n, m, x, y, i;

    fin >> n >> m;
    for (i = 1; i<=4*n; i++)
        a[i] = {-1ll<<50, -1ll<<50, -1ll<<50, 0};

    constr (1, 1, n);
    for (i = 1; i<=m; i++)
    {
        fin >> x >> y;
        fout << query (1, 1, n, x, y).smax << '\n';
    }
    return 0;
}