#include <cstdio>
#include <fstream>
#define nmax 100005
using namespace std;
ifstream f("sequencequery.in");
ofstream g("sequencequery.out");
struct nod {long long s;long long st;long long dr;long long ss;};
nod aux,aux2;
bool prim;
long long maxim;
nod a[4*nmax];
int v[nmax],x,y;



nod alipeste(nod a,nod b)
{
    nod c;
    c.s=0;c.st=0;c.dr=0;c.ss=0;

    c.s=a.s+b.s;

    c.st=max(a.st,a.s+b.st);

    c.dr=max(b.dr,b.s+a.dr);

    c.ss=max( max(a.ss,b.ss), a.dr+b.st   );

    return c;
}

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

    if (st==dr) {
        a[nod].s=v[st];
        a[nod].st=v[st];
        a[nod].dr=v[st];
        a[nod].ss=v[st];
        return;
    }
    int mid= (st+dr)>>1;

    build(nod*2 , st , mid);
    build(nod*2+1 , mid+1 ,dr);
    a[nod]=alipeste(a[nod*2],a[nod*2+1]);
}
void query(int nod , int st, int dr) {

    if (x<=st&&dr<=y) {
        if (prim==false) {
            prim=true;
            aux=a[nod];
        }
        else {
            aux=alipeste(aux,a[nod]);
        }
        return;
    }

    int mid=(st+dr)>>1;

    if (x<=mid) {
        query(2*nod,st,mid);
    }
    if (y>mid) {
        query(2*nod+1,mid+1,dr);
    }


}



int main()
{
    int n,m;
    int i,j;
    f>>n>>m;
    for (i=1;i<=n;i++)
        f>>v[i];

    build(1,1,n);
    for (m;m>=1;m--) {
        f>>x>>y;
        prim=false;
        maxim=0;
        query(1,1,n);
        g<<aux.ss<<'\n';
    }
    return 0;
}