#include<bits/stdc++.h>
using namespace std;
const int N=5e4+5;
int mn[N][22],mx[N][22];

void ST(int x){
	for(int j=1;(1<<j)<=x;j++){
		for(int i=1;i+(1<<j)-1<=x;i++){
			mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
			mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
		}
	}
	
}

int main(){
	int n,q,ansn[N],ansx[N],l,r,k;
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>mn[i][0];
		mx[i][0]=mn[i][0];
	}
	ST(n);
	for(int i=1;i<=q;i++){
		cin>>l>>r;
		k=log2(r-l+1);
		ansn[i]=min(mn[l][k],mn[r-(1<<k)+1][k]);
		ansx[i]=max(mx[l][k],mx[r-(1<<k)+1][k]);
	}
	for(int i=1;i<=q;i++) cout<<ansx[i]-ansn[i]<<endl;
	return 0;
}