#include<fstream>

#define MAXN 100001
#define INF 922337203685477580


using namespace std;
typedef int64_t var;

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

var n;

inline var zeros(const var &i) {
    return (i&(-i));
}
var SUM[MAXN];
void add(var ind, var val) {
    for(; ind <= n; ind += zeros(ind)) {
        SUM[ind] += val;
    }
}
var findsum(var ind) {
    var s=0;
    for(;ind;ind -= zeros(ind)) {
        s+=SUM[ind];
    }
    return s;
}

var findelem(var ind) {
    return findsum(ind) - findsum(ind-1);
}

var MAX[2*MAXN], BEG[2*MAXN], END[2*MAXN];

struct Trip {
    var b, m, e;
    Trip(var a, var d, var c) {
        b = a; m = d; e = c;
    }
};

void build(var node, var b, var e) {
    if(b==e) {
        BEG[node] = findelem(b);
        END[node] = BEG[node];
        MAX[node] = BEG[node];
        }
    else {
        var m = (b+e)/2;
        build(node*2, b, m);
        build(node*2+1, m+1, e);

        BEG[node] = BEG[node*2+1] + findsum(m) - findsum(b-1);
        BEG[node] = max(BEG[node*2], BEG[node]);

        END[node] = END[node*2] + findsum(e) - findsum(m);
        END[node] = max(END[node], END[node*2+1]);

        MAX[node] = max(MAX[node*2], MAX[node*2+1]);
        MAX[node] = max(MAX[node], END[node*2] + BEG[node*2+1]);
    }
}

Trip query(var node, var b, var e, var l, var r) {
    if(b>r || e<l) return Trip(-INF, -INF, -INF);
    if(b>=l && e<=r) return Trip(BEG[node], MAX[node], END[node]);
    else {
        var m = (b+e)/2;
        Trip t1 = query(node*2, b, m, l, r);
        Trip t2 = query(node*2+1, m+1, e, l, r);

        var B, E, M;

        B = t2.b + findsum(m) - findsum(b-1);
        B = max(B, t1.b);

        E = t1.e + findsum(e) - findsum(m);
        E = max(E, t2.e);

        M = max(t1.m, t2.m);
        M = max(M, t1.e+t2.b);
        return Trip(B, M, E);
    }
}





int main() {
    var m;
    fin>>n>>m;
    var B, E, M;
    var a, b;
    for(var i=1; i<=n; i++) {
        fin>>a;
        add(i, a);
    }
    build(1, 1, n);
    while(m--) {
        fin>>a>>b;
        Trip t=query(1, 1, n, a, b);
        fout<<t.m<<'\n';
    }

    return 0;
}