#include<bits/stdc++.h>
using namespace std;
inline int in(){
     register int x=0,f=1,a;
     char ch=getchar();
     while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
     while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
     return a=x*f;
}
int n,m,a[100005],st[100005][35],aq[100005],stw[100005][35];
int ga(int l,int r){
	int k=log2(r-l+1);
	int mx=max(st[l][k],st[r-(1<<k)+1][k]);
	int mi=min(stw[l][k],st[r-(1<<k)+1][k]);
	return mx-mi;
}
int main(){
	n=in(),m=in();
	for(register int i=1;i<=n;i++) a[i]=in();
//	memset(stw,0x7f,sizeof(stw));
	for(register int i=1;i<=n;i++) st[i][0]=a[i],stw[i][0]=a[i];
	for(register int j=1;(1<<j)<=n;j++){
		for(int i=1;i+(1<<j)-1<=n;i++){
			st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
			stw[i][j]=min(stw[i][j-1],stw[i+(1<<(j-1))][j-1]);
		}
	}
	for (register int i=1;i<=m;i++) {
		int x=in(),y=in();
		printf ("%d\n",ga(x,y));
	}
}