#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(nod*2, st, m);
        else
            Update(nod*2+1, m+1, dr);
        //
        Arb[nod].Sst = max(Arb[2*nod].Sst, Arb[2*nod].Sum + Arb[2*nod+1].Sst);
        Arb[nod].Sdr = max(Arb[2*nod+1].Sdr, Arb[2*nod+1].Sum + Arb[2*nod].Sdr);
        Arb[nod].Sum = Arb[2*nod].Sum + Arb[2*nod+1].Sum;
        Arb[nod].Ssm = max(Arb[2*nod].Ssm, max(Arb[2*nod+1].Ssm, Arb[2*nod+1].Sst + Arb[2*nod].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;
    cin >> N >> M;
    for(int i=1; i<=N; i++) {
        cin >> val;
        poz = i;
        Update(1, 1, N);
    }
    //
    while(M--) {
        cin >> x >> y;
        sec = sol = -INF;
        Query(1, 1, N);
        cout << sol << '\n';
    }
    //
    f.close();
    g.close();
    return 0;
}