#include<iostream>
using namespace std;
int n,q,a,b,lis[114514],trem[114514],tren[114514];
inline int lbt(int num){return num&(-num);}
void updt(int id,int num){
	while(id<=n){
		trem[id]=num;tren[id]=num;
		for(int i=1;i<lbt(id);i<<=1){
			if(trem[id]<trem[id-i]){trem[id]=trem[id-i];}
			if(tren[id]>tren[id-i]){tren[id]=tren[id-i];}
		}
		id+=lbt(id);
	}
}
void qjc(int l,int r){
	int ma=-1,mi=114514;
	while(l<=r){
		if(ma<lis[r]){ma=lis[r];}
		if(mi>lis[r]){mi=lis[r];}
		r--;
		while(r-l>=lbt(r)){
			if(ma<trem[r]){ma=trem[r];}
			if(mi>tren[r]){mi=tren[r];}
			r-=lbt(r);
		}
	}
	printf("%d\n",ma-mi);
}
int main(){
	scanf("%d %d",&n,&q);
	for(int i=1;i<=n;i++){
		scanf("%d",&lis[i]);
		updt(i,lis[i]);
	}
	while(q--){
		scanf("%d %d",&a,&b);
		if(b<a){a+=b;b=a-b;a-=b;}
		qjc(a,b);
	}
	return/*结束*/0;
}