#include<fstream>
#define INF 1000001
#define MAXN 100001

using namespace std;

typedef int64_t var;

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

var V[MAXN], n;

struct nod {
    var l, r, m;
    bool is, id;
    nod(var s) {
        l = r = m = s;
        is = id = 1;
    }
    nod() {nod(0);}
} TREE[3*MAXN];

void update(nod &rez, const nod &n1, const nod &n2) {
    rez.m = max(n1.m, n2.m);
            rez.l = n1.l;
            rez.r = n2.r;
    rez.id = rez.is = 0;
    if(n1.is && n2.l > 0) {
        rez.l += n2.l;
        if(n2.is) {
            rez.is = 1;
        }
    }
    if(n2.id && n1.r > 0) {
        rez.r += n1.r;
        if(n1.id) {
             rez.id = 1;
        }
    }

    if(rez.m <= n1.r + n2.l) {
        rez.m = n1.r + n2.l;

        if(n1.id) {
            rez.l = rez.m;
        }
        if(n2.is) {
            rez.r = rez.m;
        }
    }
}

void buildtree(var node, var b, var e) {
    if(b == e) {
        TREE[node] = nod(V[b]);
    } else {
        var mid = (b+e)/2;

        buildtree(node*2, b, mid);
        buildtree(node*2+1, mid+1, e);

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


nod findmax(var node, var b, var e, var l, var r) {
    if(b>r || e<l) return nod(-INF);
    if(b>=l && e<=r) return TREE[node];
    var mid = (b+e)/2;
    nod n1 = findmax(node*2, b, mid, l, r);
    nod n2 = findmax(node*2+1, mid+1, e, l, r);
    nod rez;

    update(rez, n1, n2);
    return rez;
}

int main() {
    var q, a, b;
    fin>>n>>q;
    for(var i=1; i<=n; i++) {
        fin>>V[i];
    }
    buildtree(1, 1, n);
    while(q--) {
        fin>>a>>b;
        nod rez = findmax(1, 1, n, a, b);
        fout<<rez.m<<'\n';
    }
    return 0;
}