#include<fstream>

using namespace std;

const char iname[]="maxq.in";
const char oname[]="maxq.out";
const int maxn=100005;

ifstream f(iname);
ofstream g(oname);

struct elem
{
    long long s,ls,ld,l;
    void update(elem x,elem y)
    {
        s=x.s+y.s;
        ls=max(x.s+y.ls,x.ls);
        ld=max(y.s+x.ld,y.ld);
        l=max(max(max(ls,ld),max(x.l,y.l)),x.ld+y.ls);
    }
} arb[maxn*3];

int n,m,i,j,x,y,z;

void update(int nod,int left,int right,int poz,int value)
{
    if(left==right)
    {
        arb[nod].s=arb[nod].ls=arb[nod].ld=arb[nod].l=value;
        return;
    }
    int mid=(left+right)>>1;
    if(poz<=mid)
        update(nod*2,left,mid,poz,value);
    else
        update(nod*2+1,mid+1,right,poz,value);
    arb[nod].update(arb[nod*2],arb[nod*2+1]);
}

elem query(int nod,int left,int right,int start,int finish)
{
    if(start<=left&&right<=finish)
        return arb[nod];
    int mid=(left+right)>>1;
    if(start<=mid&&mid<finish)
    {
        elem b;
        b.update(query(nod*2,left,mid,start,finish),query(nod*2+1,mid+1,right,start,finish));
        return b;
    }
    else
        if(start<=mid)
            return query(nod*2,left,mid,start,finish);
        else
            return query(nod*2+1,mid+1,right,start,finish);
}
int main()
{
    f>>n>>m;
    for(i=1;i<=n;++i)
        f>>x,update(1,1,n,i,x);
    for(i=1;i<=m;++i)
    {
        f>>y>>z;
        g<<query(1,1,n,y+1,z+1).l<<"\n";
    }
}