#include <fstream>

using namespace std;

struct nod {
    int ss;
    int st;
    int dr;
    int su;
};

nod A[400010];
int V[1000010];
ifstream fin ("sequencequery.in");
ofstream fout("sequencequery.out");

int n, m, i, a, b;

void build (int st, int dr, int nod) {
    if (st == dr) {
        A[nod].ss = A[nod].dr = A[nod].st = A[nod].su = V[st];
    } else {
        int mid = (st + dr)/2;
        build(st, mid, 2*nod);
        build(mid+1, dr, 2*nod+1);
        A[nod].su = A[2*nod].su + A[2*nod+1].su;
        A[nod].ss = max ( A[2*nod].dr + A[2*nod+1].st , max(A[2*nod].ss, A[2*nod+1].ss)  );
        A[nod].st = max(A[2*nod].st, A[2*nod].su + A[2*nod+1].st);
        A[nod].dr = max(A[2*nod+1].dr, A[2*nod].dr + A[2*nod+1].su);
    }
}

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

            r.su = left.su + right.su;
            r.ss = max ( left.dr + right.st , max(left.ss, right.ss)  );
            r.st = max(left.st, left.su + right.st);
            r.dr = max(right.dr, left.dr + right.su);
            return r;

        } else
            if (ins == 1)
                return left;
            else
                return right;
    }
}

int main() {
    fin>>n>>m;
    for (i=1;i<=n;i++)
        fin>>V[i];

    build(1, n, 1);
    for (i=1;i<=m;i++) {
        fin>>a>>b;
        nod r = query(1, n, 1, a, b);
        fout<<r.ss<<"\n";
    }
}