#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>

using namespace std;

int n,q,l,r,lqq,ne2;
int st[17][51000],stmx[20][51000];

int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
    {
            scanf("%d",&st[0][i]);
            stmx[0][i]=st[0][i];
    }
    ne2=log((double)n)/log(2.0);
    for(int i=1;i<=ne2;i++)
    {
            int mxj=n-(1<<i)+1,lq=1<<(i-1);
            for(int j=1;j<=mxj;j++)
            {st[i][j]=min(st[i-1][j+lq],st[i-1][j]);
            stmx[i][j]=max(stmx[i-1][j+lq],stmx[i-1][j]);
            }
    }
    for(int i=1;i<=q;i++)
    {
            scanf("%d%d",&l,&r);lqq=log((double)r-l)/log(2.0);
            printf("%d\n",max(stmx[lqq][l],stmx[lqq][r+1-(1<<lqq)])-min(st[lqq][l],st[lqq][r+1-(1<<lqq)]));
    }
    return 0;
}