#include <fstream>

using namespace std;

ifstream f("sequencequery.in");
ofstream g("sequencequery.out");

struct AINT
{
    long long ssm, pref, suf, sum;
}aint[1000005];

long long n, m, a[200005];

void clean(AINT a){
    a = {0, 0, 0, 0};
}

AINT update_nod(AINT a1, AINT a2)
{
    AINT ans; clean(ans);
    ans.pref = max(a1.pref, a1.sum + a2.pref);
    ans.suf = max(a2.suf, a2.sum + a1.suf);
    ans.ssm = max(a1.suf + a2.pref, max(a1.ssm, a2.ssm));
    ans.sum = a1.sum + a2.sum;

    return ans;
}

void update_frunza(long long nod, long long x){
    aint[nod] = {x, x, x, x};
}

void update(long long nod, long long st, long long dr, long long poz, long long x)
{
    if(st == dr)
        update_frunza(nod, x);
    else
    {
        long long mij = (st + dr) / 2;
        if(poz <= mij)
            update(2 * nod, st, mij, poz, x);
        else
            update(2 * nod + 1, mij + 1, dr, poz, x);

        aint[nod] = update_nod(aint[2 * nod], aint[2 * nod + 1]);
    }
}

AINT query(long long nod, long long st, long long dr, long long x, long long y)
{
    if(x <= st && dr <= y)
        return aint[nod];

    else
    {
        long long mij = (st + dr) / 2;
        AINT ans, a1, a2; long long ok1 = 0, ok2 = 0;
        clean(ans); clean(a1); clean(a2);

        if(x <= mij)
            a1 = query(2 * nod, st, mij, x, y), ok1 = 1;

        if(y > mij)
            a2 = query(2 * nod + 1, mij + 1, dr, x, y), ok2 = 1;

        if(ok1 && !ok2)
            ans = a1;

        else if(!ok1 && ok2)
            ans = a2;

        else if(ok1 && ok2)
            ans = update_nod(a1, a2);

        return ans;
    }
}

int main()
{
    f >> n >> m;
    for(long long i = 1; i <= n; i ++)
    {
        long long x; f >> x;
        update(1, 1, n, i, x);
    }

    for(long long i = 1; i <= m; i ++)
    {
        long long x, y;
        f >> x >> y;
        AINT ans = query(1, 1, n, x, y);
        g << ans.ssm << '\n';
    }
    return 0;
}