#include<bits/stdc++.h>
using namespace std;
const int N = 5e4+10;
#define int long long
int n,q,a[N],minn_2,maxn_2;
struct T{
    int l;
    int r;
    int minn;
    int maxn;
}t[N*4];
inline void build(int i,int l,int r){
    t[i].l=l;
    t[i].r=r;
    if(l==r){
        t[i].minn=a[l];
        t[i].maxn=a[r];
        return;
    }
    int mid=(l+r)>>1;
    build(i*2,l,mid);
    build(i*2+1,mid+1,r);
    t[i].minn=min(t[i*2].minn,t[i*2+1].minn);
    t[i].maxn=max(t[i*2].maxn,t[i*2+1].maxn);
}
inline void query(int i,int l,int r){
    if(t[i].l==t[i].r){
        maxn_2=max(maxn_2,t[i].maxn);
        minn_2=min(minn_2,t[i].minn);
        return;
    }
    if(t[i*2].r>=r){
        query(i*2,l,r);
    }
    else if(t[i*2+1].l<=l){
        query(i*2+1,l,r);
    }
    else query(i*2,l,t[i*2].r),query(i*2+1,t[i*2+1].l,r);
}
signed main(){
    ios::sync_with_stdio(false);
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);
    for(int i=1;i<=q;i++){
        int x,y;
        minn_2=1e9;
        maxn_2=0;
        cin>>x>>y;
        query(1,x,y);
        cout<<maxn_2-minn_2<<endl;
    }
    return 0;
}