#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 Arb[4*NMAX + 1];
int A[NMAX+1], x, y;
long long sec, sol;

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