#include<bits/stdc++.h>
using namespace std;

struct cell
{
    long long st,best,dr;
};

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

const int NMAX=100005;

int n,m,a[NMAX];
long long sum[NMAX];
cell aint[4*NMAX];
//pt query
bool ok;
cell k,l;

inline void CreateAint(int nod,int stanga,int dreapta)
{
    if (stanga==dreapta) aint[nod].st=aint[nod].best=aint[nod].dr=a[stanga];
    else
        {
            int i,mij=(stanga+dreapta)>>1;
            long long minimal=1LL<<50;
            CreateAint(2*nod,stanga,mij);
            CreateAint(2*nod+1,mij+1,dreapta);

            //stanga
            aint[nod].st=a[stanga];
            for (i=stanga+1;i<=dreapta;i++)
                aint[nod].st=max(aint[nod].st,sum[i]-sum[stanga-1]);

            //dreapta
            aint[nod].dr=a[dreapta];
            for (i=dreapta-1;i>=stanga;i--)
                aint[nod].dr=max(aint[nod].dr,sum[dreapta]-sum[i-1]);

            //best
            aint[nod].best=minimal=a[stanga];
            for (i=stanga+1;i<=dreapta;i++)
                {
                    aint[nod].best=max(aint[nod].best,sum[i]-sum[stanga-1]);
                    aint[nod].best=max(aint[nod].best,sum[i]-sum[stanga-1]-minimal);
                    minimal=min(minimal,sum[i]-sum[stanga-1]);
                }

        }
}

inline void Query(int nod,int stanga,int dreapta,int x,int y)
{
    if (x<=stanga && dreapta<=y)
        {
            if (ok==0)
                {
                    ok=1;
                    k=aint[nod];
                    //fout<<k.st<<" "<<k.best<<" "<<k.dr<<"\n";
                    return ;
                }
            //fout<<aint[nod].st<<" "<<aint[nod].best<<" "<<aint[nod].dr<<"\n";
            //combinam
            l.st=max(k.st,sum[stanga-1]-sum[x-1]+aint[nod].st);

            l.dr=max(aint[nod].dr,sum[dreapta]-sum[stanga-1]+k.dr);

            l.best=max(k.best,aint[nod].best);
            l.best=max(l.best,max(l.st,l.dr));
            l.best=max(l.best,k.dr+aint[nod].st);

            k=l;
        }
    else
        {
            int mij=(stanga+dreapta)>>1;

            if (x<=mij) Query(2*nod,stanga,mij,x,y);
            if (y>mij) Query(2*nod+1,mij+1,dreapta,x,y);
        }
}

int main()
{
    int i,x,y;
    fin>>n>>m;
    for (i=1;i<=n;i++)
        {
            fin>>a[i];
            sum[i]=sum[i-1]+a[i];
        }
    CreateAint(1,1,n);
    for (i=1;i<=m;i++)
        {
            fin>>x>>y;
            ok=0;
            Query(1,1,n,x,y);
            fout<<k.best<<"\n";
        }
    return 0;
}