#include <bits/stdc++.h>
using namespace std;

const int NMAX = 100005;

struct NOD {
    int mid, sum, left, right; };

int n, m, x, y, now, best, pos, val;

NOD pom[NMAX*4]; ///Sorry, Tamio...

void update(int nod, int st, int dr) {
    if(st==dr) {
        pom[nod] = {val, val, val, val};
        return; }

    int med = (st+dr)/2;
    if(pos<=med) update(nod*2, st, med);
    else update(nod*2+1, med+1, dr);

    pom[nod].sum = pom[2*nod].sum + pom[2*nod+1].sum;
    pom[nod].mid = max(pom[2*nod].right+pom[2*nod+1].left, max(pom[2*nod].mid, pom[2*nod+1].mid));
    pom[nod].left = max(pom[2*nod].left, pom[2*nod].sum+pom[2*nod+1].left);
    pom[nod].right = max(pom[2*nod+1].right, pom[2*nod+1].sum+pom[2*nod].right);
}

void query(int nod, int st, int dr) {
    if(x<=st && dr<=y) {
        now = max(now, 0);
        best = max(best, pom[nod].left+now);
        best = max(best, pom[nod].mid);
        now = max(now+pom[nod].sum, pom[nod].right);
        return;
    }
    int med = (st+dr)/2;

    if(x<=med) query(2*nod, st, med);
    if(med<y) query(2*nod+1, med+1, dr);
}

int main(void) {
    ifstream fi("sequencequery.in");
    ofstream fo("sequencequery.out");

    fi >> n >> m;
    for(pos=1; pos<=n; ++pos) {
        fi >> val;
        update(1, 1, n); }

    for(int i=1; i<=m; ++i) {
        best = -1e9;
        now = 0;

        fi >> x >> y;
        query(1, 1, n);
        fo << best << '\n';
    }

    return 0;
}