#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=50010;
int n,m,a[maxn],mm[maxn][20],mi[maxn][20];
void get()
{
    for(int i=1;i<=n;i++)
        mm[i][0]=mi[i][0]=a[i];
    for(int j=1;(1<<j)<=n;j++)
        for(int i=1;i+(1<<j)<=n+1;i++)
            {
                mm[i][j]=max(mm[i][j-1],mm[i+(1<<(j-1))][j-1]);
                mi[i][j]=min(mi[i][j-1],mi[i+(1<<(j-1))][j-1]);
            }
}
int rmq(int l,int r)
{
    int k=0;
    while((1<<(k+1))<=r-l+1)
        k++;
    int ans1=max(mm[l][k],mm[r-(1<<k)+1][k]);
    int ans2=min(mi[l][k],mi[r-(1<<k)+1][k]);
    //cout << ans1  << endl << ans2 <<  endl;
    return ans1-ans2;
}
int main()
{
    while(~scanf("%d %d",&n,&m))
    {
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        memset(mm,0,sizeof(mm));
        memset(mi,0,sizeof(mi));
        get();
        for(int i=0;i<m;i++)
            {
                int l,r;
                scanf("%d %d",&l,&r);
                int pos=rmq(l,r);
                printf("%d\n",pos);
            }
    }
    return 0;
}