#include <fstream>
#define INF 10000000LL

using namespace std;

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

long long max (long long a, long long b) {
    if (a>b)
        return a;
    return b;
}

struct data {
    long long m;
    long long l;
    long long r;
    long long s;
}v[400010];

int n,m,a,b,x,i;

void update (int nod, int st, int dr) {

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

    v[nod].m= max(v[2*nod].m , max(v[2*nod+1].m, v[2*nod].r+v[2*nod+1].l));
    v[nod].l=max(v[2*nod].l , v[2*nod].s+v[2*nod+1].l);
    v[nod].r=max(v[2*nod+1].r , v[2*nod+1].s+v[2*nod].r);
    long long sum=0;
    if (v[2*nod].s!=-INF && v[2*nod+1].s!=-INF)
        sum=v[2*nod].s+v[2*nod+1].s;
    else
        sum=v[2*nod].s+v[2*nod+1].s+INF;
        v[nod].s=sum;

}

data query (int nod, int st, int dr ){

    data qs,qd,rez;

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


int main () {

    fin>>n>>m;
    for (i=1;i<=4*n;i++)
        v[i].m=v[i].l=v[i].r=v[i].s=-INF;

    for (i=1;i<=n;i++) {
        fin>>x;
        update (1,1,n);
    }
    while(m--){
        fin>>a>>b;
        data c=query (1,1,n);
        fout<<c.m<<"\n";
    }


    return 0;
}