#include<bits/stdc++.h>
#define maxn 50005
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r>>1)
#define INF 0x3f3f3f3f
using namespace std;
int N,Q;
int arr[maxn];
int mx[maxn<<2],mi[maxn<<2];
void Build(int rt,int l,int r)
{
    if(l==r)
    {
        mx[rt]=mi[rt]=arr[l];
        return;
    }
    Build(ls,l,mid);
    Build(rs,mid+1,r);
    mx[rt]=max(mx[ls],mx[rs]);
    mi[rt]=min(mi[ls],mi[rs]);
}
int Max(int rt,int l,int r,int s,int t)
{
    if(s>r||t<l)
        return -INF;
    if(s<=l&&r<=t)
        return mx[rt];
    return max(Max(ls,l,mid,s,t),Max(rs,mid+1,r,s,t));
}
int Min(int rt,int l,int r,int s,int t)
{
    if(s>r||t<l)
        return INF;
    if(s<=l&&r<=t)
        return mi[rt];
    return min(Min(ls,l,mid,s,t),Min(rs,mid+1,r,s,t));
}
int main()
{
    freopen("lineup.in","r",stdin);
    freopen("lineup.out","w",stdout);
    scanf("%d%d",&N,&Q);
    for(int i=1;i<=N;i++) 
        scanf("%d",&arr[i]);//读入一波
    Build(1,1,N);
    while(Q--)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%d\n",Max(1,1,N,l,r)-Min(1,1,N,l,r));    
    }
    return 0;
}