#include <iostream>
#include <fstream>
using namespace std;

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

const int NMAX = 100000;
const long long INF = (1LL << 62);

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

nodArb Arb[4*NMAX + 1];
int val, x, y, poz;
long long sec, sol;

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 && dr <= y) {
        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 (m < y)
            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 = -INF;
        Query(1, 1, N);
        g << sol << '\n';
    }
    //
    f.close();
    g.close();
    return 0;
}