#include <iostream>
#include <fstream>
#define nmax 100002
#define inf 10000000001
using namespace std;
struct arbore_intervale{
    long long ssm,spref,ssuf;
};
arbore_intervale aint[4*nmax];
int n,m,v[nmax];
ifstream f("sequencequery.in");
ofstream g("sequencequery.out");
void build(int nod,int st,int dr)///build in O(nlogn)->T(n)=2*T(n/2)+0(n) recombinarea
{
    if(st==dr)
    {
        aint[nod].ssm=v[st];
        aint[nod].spref=0;
        aint[nod].ssuf=0;
        return;
    }
    int mid=(st+dr)>>1;
    build(2*nod,st,mid);
    build(2*nod+1,mid+1,dr);
    int ans=0,k=mid,l=mid+1;
    long long bestl=-inf,bestk=-inf,suml=0,sumk=0;
    if(aint[2*nod].ssm>aint[nod].ssm)
    {
        aint[nod].ssm=aint[2*nod].ssm;
        ans=1;
    }
    if(aint[2*nod+1].ssm>aint[nod].ssm)
    {
        aint[nod].ssm=aint[2*nod+1].ssm;
        ans=2;
    }
    for(int i=mid;i>=st;i--)
    {
        suml+=v[i];
        if(suml>bestl)
        {
            bestl=suml;
            l=i;
        }
    }
    for(int i=mid+1;i<=dr;i++)
    {
        sumk+=v[i];
        if(sumk>bestk)
        {
            bestk=sumk;
            k=i;
        }
    }
    if(bestl+bestk>aint[nod].ssm)
    {
        aint[nod].ssm=bestl+bestk;
        ans=3;
    }
    switch(ans)
    {
        case 1:{
            aint[nod].spref=aint[2*nod].spref;
            aint[nod].ssuf=aint[2*nod].ssuf+aint[2*nod+1].spref+aint[2*nod+1].ssm+aint[2*nod+1].ssuf;
        }break;
        case 2:{
            aint[nod].ssuf=aint[2*nod+1].ssuf;
            aint[nod].spref=aint[2*nod].spref+aint[2*nod].ssm+aint[2*nod].ssuf+aint[2*nod+1].spref;
        }break;
        case 3:{
            int sl=0,sk=0;
            for(int i=st;i<l;i++)
                sl+=v[i];
            for(int i=k+1;i<=dr;i++)
                sk+=v[i];
            aint[nod].spref=sl;
            aint[nod].ssuf=sk;
        }
    }
}
void query(int nod,int st,int dr,int a,int b,long long&dp,long long&sufix,long long&smax)
{
    if(st>dr)
        return;
    if(dr<a||st>b)
        return;
    if(a<=st&&dr<=b)
    {
        long long dpcurr;
        dpcurr=aint[nod].ssm;
        long long add=aint[nod].spref+sufix+dp;
        if(add>0)
        {
            dpcurr+=add;
        }
        if(dpcurr>smax)
            smax=dpcurr;
        dp=dpcurr;
        sufix=aint[nod].ssuf;
        return;
    }
    int mid=(st+dr)>>1;
    query(2*nod,st,mid,a,b,dp,sufix,smax);
    query(2*nod+1,mid+1,dr,a,b,dp,sufix,smax);
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=n;i++)
        f>>v[i];
    for(int i=1;i<=4*n;i++)
        aint[i].ssm=aint[i].spref=aint[i].ssuf=-inf;
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int a,b;
        long long smax=-inf,dpcurr=0,sufix=0;
        f>>a>>b;
        query(1,1,n,a,b,dpcurr,sufix,smax);
        g<<smax<<"\n";
    }
    return 0;
}