#include <fstream>

using namespace std;
ifstream cin("sequencequery.in");
ofstream cout("sequencequery.out");
int spar[200005];
int v[200005];
int minim[200005];
int maxim[200005];
int smax[200005];
int smin[200005];
int contain[200005];
void buildcontains(int node,int st,int dr)
{
    if(st==dr)
    {
        maxim[node]=v[st];
        minim[node]=v[st];
        contain[node]=v[st]-v[st-1];
        cout<<st<<" "<<dr<<" "<<contain[node]<<'\n';
        return;
    }
    else
    {
        int mij=(st+dr)/2;
        buildcontains(node*2,st,mij);
        buildcontains(node*2+1,mij+1,dr);
        contain[node]=max(contain[node*2],contain[node*2+1]);
        contain[node]=max(contain[node],maxim[node*2+1]-min(minim[node*2],v[st-1]));
        maxim[node]=max(maxim[node*2],maxim[node*2+1]);
        minim[node]=min(minim[node*2],minim[node*2+1]);
        cout<<st<<" "<<dr<<" "<<contain[node]<<'\n';
        return ;
    }
}
long long inf=1e14;
int cnt=0;
struct structura
{
    int minim,maxim;
};
structura vec[1000005];
long long querry (int node,int st,int dr,int qst,int qdr)
{
    if(qst<=st && dr<=qdr)
    {
        cnt++;
        vec[cnt].minim=minim[node];
        vec[cnt].maxim=maxim[node];
        return contain[node];
    }
    else if(st>qdr || dr<qst)
    {
        return -inf;
    }
    else
    {
        int mij=(st+dr)/2,val1,val2;
        val1=querry(node*2,st,mij,qst,qdr);
        val2=querry(node*2+1,mij+1,dr,qst,qdr);
        return max(val1,val2);
    }
}
int main()
{
    int n,i,j,k,q,x,y,val;
    cin>>n>>q;
    v[1]=0;
    spar[1]=0;
    for(i=1; i<=n; i++)
    {
        cin>>v[i];
        spar[i]=spar[i-1]+v[i];
    }
    for(i=1; i<=n; i++)
    {
        v[i]=spar[i];
    }
    buildcontains(1,1,n);
    for(i=1; i<=q; i++)
    {
        cin>>x>>y;
        if(x>y)
        {
            swap(x,y);
        }
        cnt=0;
        val=querry(1,1,n,x,y);
        if(cnt>=2)
        {
            for(j=1; j<=cnt; j++)
            {
                smin[cnt]=inf;
                smax[cnt]=-inf;
            }
            smin[1]=vec[1].minim;
            for(j=2; j<=cnt; j++)
            {
                smin[j]=min(smin[j-1],vec[j].minim);
            }
            smax[cnt]=vec[cnt].maxim;
            for(j=n-1;j>=1;j--)
            {
                smax[j]=max(smax[j+1],vec[j].maxim);
            }
            for(j=1;j<n;j++)
            {
                val=max(val,smax[j+1]-smin[j]);
            }
        }
        cout<<val<<'\n';
    }
    return 0;
}