#include <fstream>

using namespace std;

int n,m,i,a,b;

long long x;

struct str{
    long long v;
    long long l;
    long long r;
    long long s;
}v[400005];

inline long long maxim(long long a, long long b) {
    return a>b ? a : b;
}

void update(int nod, int st, int dr) {
    if(st==dr) {
        v[nod].v=x;
        v[nod].s=x;
        v[nod].l=x;
        v[nod].r=x;
        return;
    }
    int mid=(st+dr)/2;
    if(i<=mid)
        update(nod*2,st,mid);
    else
        update(2*nod+1,mid+1,dr);

    v[nod].v=maxim(v[nod*2].v,maxim(v[2*nod+1].v,v[2*nod].r+v[2*nod+1].l));
    v[nod].l=maxim(v[2*nod].l,v[2*nod].s+v[2*nod+1].l);
    v[nod].r=maxim(v[2*nod+1].r,v[2*nod+1].s+v[2*nod].r);
    if(v[2*nod].s!=-1000000 && v[2*nod+1].s!=-1000000)
        v[nod].s=v[2*nod].s+v[2*nod+1].s;
    else
       v[nod].s=v[2*nod].s+v[2*nod+1].s+1000000;
}

str query(int nod, int st, int dr) {
    if(a<=st && b>=dr) {
        return v[nod];
    }
    int mid=(st+dr)/2;
    str qs, qd;
    int ok1 = 0, ok2 = 0;
    if(a<=mid) {
        qs=query(2*nod,st,mid);
        ok1 = 1;
    }
    if(b>mid) {
        qd=query(2*nod+1,mid+1,dr);
        ok2 = 1;
    }
    str rez;
    if (ok1 + ok2 == 2) {
        rez.v = maxim(qs.v, maxim(qd.v, qs.r + qd.l));
        rez.s=qs.s+qd.s;
        rez.l=maxim(qs.l,qs.s+qd.l);
        rez.r=maxim(qd.r,qd.s+qs.r);
        return rez;

    } else
        if (ok1)
            return qs;
        else
            return qd;
}

int main() {
    ifstream f("sequencequery.in");
    ofstream g("sequencequery.out");
    f>>n>>m;
    for(i=1;i<=4*n;i++)
        v[i].v=v[i].l=v[i].s=v[i].r=-1000000;

    for(i=1;i<=n;i++) {
        f>>x;
        update(1,1,n);
    }
    while(m--) {
        f>>a>>b;
        //Max=-1000000;
        g<<query(1,1,n).v<<"\n";
    }
    return 0;
}