#include <fstream>
#define  DIM 100010

using namespace std;

struct snod {
    int s;
    int sst;
    int sdr;
    int smax;
};

snod A[4*DIM];
int n, m, i, a, b;
int v[DIM];


void build(int nod, int st, int dr) {
    if (st == dr) {
        A[nod].s = A[nod].sst = A[nod].sdr = A[nod].smax = v[st];
    } else {
        int mid = (st + dr)/2;

        build(2*nod, st, mid);
        build(2*nod+1, mid+1, dr);

        A[nod].s = A[2*nod].s + A[2*nod+1].s;
        A[nod].sst = max(A[2*nod].sst, A[2*nod].s + A[2*nod+1].sst);
        A[nod].sdr = max(A[2*nod + 1].sdr, A[2*nod].sdr + A[2*nod+1].s);
        A[nod].smax = max( A[2*nod].smax, max( A[2*nod+1].smax ,  A[2*nod].sdr + A[2*nod+1].sst  )  );
    }
}

snod query(int nod, int st, int dr, int a, int b) {
    snod r;
    if (a <=st && dr <=b) {
        return A[nod];
    } else {
        int mid = (st+dr)/2;
        snod left, right;
        int okst = 0, okdr = 0;
        if (a <= mid) {
            left = query(2*nod, st, mid, a, b);
            okst = 1;
        }
        if (b > mid) {
            right = query(2*nod+1, mid+1, dr, a, b);
            okdr = 1;
        }

        if (okst == 0)
            return right;
        else
            if (okdr == 0)
                return left;
            else {

                r.s = left.s + right.s;
                r.sst = max(left.sst, left.s + right.sst);
                r.sdr = max(right.sdr, right.s + left.sdr);
                r.smax = max ( left.sdr + right.sst, max(left.smax, right.smax) );

                return r;
            }

    }

}

int main() {
    ifstream fin("sequencequery.in");
    ofstream fout("sequencequery.out");

    fin>>n>>m;
    for (i=1;i<=n;i++)
        fin>>v[i];
    build(1, 1, n);
    for (i=1;i<=m;i++) {
        fin>>a>>b;
        snod rez = query(1, 1, n, a, b);
        fout<<rez.smax<<"\n";
    }


    return 0;
}