#include <fstream>

using namespace std;

struct nodArb
{
    long long Sst, Sdr, Sum, Ssm;

    nodArb(long long val = 0)
    {
        Sst = Sdr = Sum = Ssm = val;
    }
};

nodArb Arb[1 << 18];
int poz, val, x, y;
long long sec, sol;

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

void Update(int nod, int st, int dr)
{
    if(st == dr)
        Arb[nod] = nodArb(val);
    else
    {
        int m = (st + dr) / 2;
        if(poz <= m)
            Update(2 * nod, st, m);
        else
            Update(2 * nod + 1, m + 1, dr);
        //
        Arb[nod].Sst = max(Arb[nod * 2].Sst, Arb[nod * 2].Sum + Arb[nod * 2 + 1].Sst);
        Arb[nod].Sdr = max(Arb[nod * 2 + 1].Sdr, Arb[nod * 2 + 1].Sum + Arb[nod * 2].Sdr);
        Arb[nod].Sum = Arb[nod * 2].Sum + Arb[nod * 2 + 1].Sum;
        Arb[nod].Ssm = max(Arb[nod * 2].Ssm, max(Arb[nod * 2 + 1].Ssm, Arb[nod * 2 + 1].Sst + Arb[nod * 2].Sdr));
    }
}

void Query(int nod, int st, int dr)
{
    if(x <= st && y >= dr)
    {
        if(sec < 0) sec = 0;
        sol = max(sol, max(sec + Arb[nod].Sst, Arb[nod].Ssm));
        sec = max(sec + Arb[nod].Sum, Arb[nod].Sdr);
    }
    else
    {
        int m = (st + dr) / 2;
        if(x <= m)
            Query(2 * nod, st, m);
        if(y > m)
            Query(2 * nod + 1, m + 1, dr);
    }
}

int main()
{
    int N, M;
    f >> N >> M;
    for(poz = 1; poz <= N; poz++)
    {
        f >> val;
        Update(1, 1, N);
    }
    while(M--)
    {
        f >> x >> y;
        sec = sol = 1LL << 63; ///-oo
        Query(1, 1, N);
        g << sol << '\n';
    }
    return 0;
}