#include <fstream>

using namespace std;

const int NMAX = 100000;
const int MMAX = 100000;

int v[1 + NMAX];

struct Nod
{
    long long sumaTotala;
    long long ssm;
    long long sumaSt;
    long long sumaDr;

    Nod() = default;
};

Nod aint[1 + 4 * NMAX];

void buildAint(int indexNod, int st, int dr)
{
    if (st == dr)
    {
        aint[indexNod].sumaTotala = v[st];
        aint[indexNod].ssm        = v[st];
        aint[indexNod].sumaSt     = v[st];
        aint[indexNod].sumaDr     = v[st];

        return;
    }

    int mij = (st + dr) / 2;
    int indexFiuSt = 2 * indexNod;
    int indexFiuDr = 2 * indexNod + 1;

    buildAint(indexFiuSt, st, mij);
    buildAint(indexFiuDr, mij + 1, dr);

    aint[indexNod].sumaTotala = aint[indexFiuSt].sumaTotala + aint[indexFiuDr].sumaTotala;
    aint[indexNod].ssm = max(max(aint[indexFiuSt].ssm, aint[indexFiuDr].ssm), aint[indexFiuSt].sumaDr + aint[indexFiuDr].sumaSt);
    aint[indexNod].sumaSt = max(aint[indexFiuSt].sumaSt, aint[indexFiuSt].sumaTotala + aint[indexFiuDr].sumaSt);
    aint[indexNod].sumaDr = max(aint[indexFiuDr].sumaDr, aint[indexFiuSt].sumaDr + aint[indexFiuDr].sumaTotala);
}

struct returnQuery
{
    long long sumaTotala;
    long long ssm;
    long long sumaSt;
    long long sumaDr;

    returnQuery() = default;

    returnQuery(long long sumaTotala, long long ssm, long long sumaSt, long long sumaDr) :
        sumaTotala(sumaTotala), ssm(ssm), sumaSt(sumaSt), sumaDr(sumaDr) {};
};

returnQuery queryAint(int indexNod, int st, int dr, int stQ, int drQ)
{
    if (st == stQ && drQ == dr)
        return returnQuery(aint[indexNod].sumaTotala, aint[indexNod].ssm, aint[indexNod].sumaSt, aint[indexNod].sumaDr);

    int mij = (st + dr) / 2;
    int indexFiuSt = 2 * indexNod;
    int indexFiuDr = 2 * indexNod + 1;

    if (drQ <= mij)
        return queryAint(indexFiuSt, st, mij, stQ, drQ);
    else if (stQ >= mij + 1)
        return queryAint(indexFiuDr, mij + 1, dr, stQ, drQ);
    else
    {
        returnQuery a = queryAint(indexFiuSt, st, mij, stQ, mij);
        returnQuery b = queryAint(indexFiuDr, mij + 1, dr, mij + 1, drQ);

        returnQuery sol;

        sol.sumaTotala = a.sumaTotala + b.sumaTotala;
        sol.ssm = max(max(a.ssm, b.ssm), a.sumaDr + b.sumaSt);
        sol.sumaSt = max(a.sumaSt, a.sumaTotala + b.sumaSt);
        sol.sumaDr = max(b.sumaDr, a.sumaDr + b.sumaTotala);

        return sol;
    }
}

int main()
{
    ifstream in("sequencequery.in");
    ofstream out("sequencequery.out");

    int n, m;
    in >> n >> m;

    for (int i = 1; i <= n; i++)
        in >> v[i];

    buildAint(1, 1, n);

    for (int j = 1; j <= m; j++)
    {
        int st, dr;
        in >> st >> dr;

        out << queryAint(1, 1, n, st, dr).ssm << '\n';
    }

    return 0;
}