#include<bits/stdc++.h>
#define ll long long
using namespace std;
#define M 1000010;
int n,q,h,a,b;
int ma[180005],mi[180005],aa[180005];
inline int lowbit(int i){
    return i&(-i);
}
void change(int i,int h){
    for(int j=i;j<=n;j+=lowbit(j)){
        ma[j]=max(ma[j],h);
        mi[j]=min(mi[j],h);
    }
}
int maxx(int a,int b){
    if(a==b) return aa[a];
    if(a<(b-lowbit(b))){
        return max(maxx(a,b-lowbit(b)),ma[b]);
    }else{
        return max(maxx(a,b-1),aa[b]);
    }
}
int minn(int a,int b){
    if(a==b) return aa[a];
    if(a<(b-lowbit(b))){
        return min(minn(a,b-lowbit(b)),mi[b]);
    }else{
        return min(minn(a,b-1),aa[b]);
    }
}
int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    cin>>n>>q;
    for(int i=0;i<n;i++){mi[i]=M;}
    for(int i=1;i<=n;i++){
        cin>>h;
        aa[i]=h;
        change(i,h);
    }
    for(int i=0;i<q;i++){
        cin>>a>>b;
        cout<<maxx(a,b)-minn(a,b)<<"\n";
    }
    return 0;
}