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

struct cell
{
    long long mx,mn,best;
};

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;

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

            //initializare
            aint[nod].best=minimal=a[st];
            aint[nod].mx=aint[nod].mn=sum[st];
            for (i=st+1;i<=dr;i++)
                {
                    aint[nod].mx=max(aint[nod].mx,sum[i]);
                    aint[nod].mn=min(aint[nod].mn,sum[i]);
                    aint[nod].best=max(aint[nod].best,sum[i]-sum[st-1]);
                    aint[nod].best=max(aint[nod].best,sum[i]-sum[st-1]-minimal);
                    minimal=min(minimal,sum[i]-sum[st-1]);
                }
        }
}

inline void Query(int nod,int st,int dr,int x,int y)
{
    if (x<=st && dr<=y)
        {
            if (ok==0)
                {
                    ok=1;
                    k=aint[nod];
                    return ;
                }
            k.best=max(k.best,max(aint[nod].best,aint[nod].mx-k.mn));
            k.mn=min(k.mn,aint[nod].mn);
        }
    else
        {
            int mij=(st+dr)>>1;

            if (x<=mij) Query(2*nod,st,mij,x,y);
            if (y>mij) Query(2*nod+1,mij+1,dr,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;
}