#include <bits/stdc++.h>
#define inf 2000000000
using namespace std;
ifstream f("sequencequery.in");
ofstream g("sequencequery.out");
struct interval
{
    int  stn,drt;
    long long best, minim, maxim;
};
interval arb[800001];
int n,x,q,a[200001],b[200001];
long long minpref;
void update(int po, int st, int dr)
{
    if(st==dr)
    {
        if(st!=0)
        {
            arb[po].stn=st;
            arb[po].drt=dr;
            arb[po].maxim=a[st];
            arb[po].minim=a[st];
            arb[po].best=a[st]-a[st-1];
        }
        else
        {
            arb[po].stn=st;
            arb[po].drt=dr;
            arb[po].best=0;
            arb[po].minim=0;
            arb[po].maxim=0;
        }
        return ;
    }
    arb[po].stn=st;
    arb[po].drt=dr;
    arb[po].best=-inf;
    arb[po].maxim=-inf;
    arb[po].minim=inf;
    int mij=(st+dr)/2;
    update(2*po,st,mij);
    update(2*po+1,mij+1,dr);
    arb[po].maxim=max(arb[2*po].maxim,arb[2*po+1].maxim);
    arb[po].minim=min(arb[2*po].minim,arb[2*po+1].minim);
    arb[po].best=max(arb[2*po].best,max(arb[2*po+1].best,(arb[2*po+1].maxim-arb[2*po].minim)));
}
int interogare(int po, int st, int dr, int a, int b)
{
    if(a<=st&&dr<=b)
    {
        long long maxx=arb[po].best;
        if(minpref!=inf)
        {
            maxx=max(maxx,arb[po].maxim-minpref);
        }
        minpref=min(minpref,arb[po].minim);
        return maxx;
    }
    int mij=(st+dr)/2;
    if(a<=mij&&b>mij) return max(interogare(2*po,st,mij,a,b),interogare(2*po+1,mij+1,dr,a,b));
    else if(a>mij) return interogare(2*po+1,mij+1,dr,a,b);
    else return interogare(2*po,st,mij,a,b);
}
int main()
{
    f>>n>>q;
    for(int i=1;i<=n;i++)
    {
        f>>a[i];
        ///a[i]=a[i-1]+b[i];
    }
    update(1,1,n);

    /**int k=1;
    while(arb[k].drt)
    {
        g<<arb[k].stn<<" "<<arb[k].drt<<" "<<arb[k].maxim<<" "<<arb[k].minim<<" "<<arb[k].best<<'\n';
        k++;
    }**/
    for(int i=1;i<=q;i++)
    {
        char c;
        int x,y;
        f>>x>>y;
        ///if(c=='1')
        //{
        minpref=inf;
        ///x++; y++;
        g<<interogare(1,1,n,x,y)<<'\n';
        //}
        ///x++; update(1,1,n);
    }
    return 0;
}