#include<fstream>
#include<limits>

#define MAXN 100001
#define INF 18446744073709


using namespace std;
typedef int64_t var;


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

var n, m;

struct Quad {
    var b, m, e, s;
    Quad(var a, var B, var c, var d) {
        b = a; m = B; e = c; s = d;
    }
    Quad() {}
};

Quad TREE[3*MAXN+1];
var A[MAXN];

Quad update(Quad l, Quad r) {
    Quad rez(-INF, -INF, -INF, -INF);
    rez.s = l.s + r.s;
    rez.b = max(l.b, r.b + l.s);
    rez.e = max(r.e, l.e + r.s);
    rez.m = max(l.m, r.m);
    rez.m = max(rez.m, l.e+r.b);

    return rez;
}

void build(var node, var b, var e) {
    if(b == e) {
        TREE[node] = Quad(A[b], A[b], A[b], A[b]);
    } else {
        var m = (b+e)/2;
        build(2*node, b, m);
        build(2*node+1, m+1, e);

        TREE[node] = update(TREE[2*node], TREE[2*node+1]);
    }
}

Quad query(var node, var b, var e, var l, var r) {
    if(b>r || e<l) return Quad(-INF, -INF, -INF, -INF);
    if(e<=r && b>=l) return TREE[node];

    var m = (b+e)/2;
    Quad q1 = query(2*node, b, m, l, r);
    Quad q2 = query(2*node+1, m+1, e, l, r);

    return update(q1, q2);
}

void updateVal(var node, var b, var e, var poz, var val) {
    if(b == e) TREE[node] = Quad(val, val, val, val);
    else {
        var m = (b+e)/2;
        if(m >= poz) updateVal(node*2, b, m, poz, val);
        else updateVal(node*2+1, m+1, e, poz, val);

        TREE[node] = update(TREE[2*node], TREE[node*2+1]);
    }
}


int main() {
    fin>>n>>m;
    var a, b, type;
    for(var i=1; i<=n; i++) {
        fin>>A[i];
    }
    build(1, 1, n);
    while(m--) {
        fin>>a>>b;
        fout<<(query(1, 1, n, a, b)).m<<'\n';
    }
    return 0;
}