#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
const int N=100000;
int n,m,a[N+5],mx[N+5],mn[N+5],bl;
int main(){
	ios::sync_with_stdio(0);
	cin>>n>>m;
	for (int i=0;i<n;i++) cin>>a[i];
	bl=(int)sqrt(n);
	memset(mn,0x7f,sizeof(mn));
	for (int i=0;i<bl;i++){
		for (int j=i*bl;j<(i+1)*bl;j++)
			mx[i]=max(mx[i],a[j]),mn[i]=min(mn[i],a[j]);
	}
	while (m--){
		int l,r,L,R,ans=0,ans1=0x7fffffff;
		cin>>l>>r; l--,r--;
		L=l/bl,R=r/bl;
		if (L==R){
			for (int i=l;i<=r;i++) ans=max(ans,a[i]),ans1=min(ans1,a[i]);
		} else {
			for (int i=L+1;i<R;i++) ans=max(ans,mx[i]),ans1=min(ans1,mn[i]);
			for (int i=l;i<(L+1)*bl;i++) ans=max(ans,a[i]),ans1=min(ans1,a[i]);
			for (int i=R*bl;i<=r;i++) ans=max(ans,a[i]),ans1=min(ans1,a[i]);
		}
//		cout<<ans<<' '<<ans1<<' ';
		cout<<ans-ans1<<'\n';
	}
}