#include<cstdio>
#include<cstring>
using namespace std;
#define MAX(x,y) (x>y?x:y)
#define MIN(x,y) (x<y?x:y)
#define Lowbit(x) (x&(-x))

int num[50010],N;
int idx_max[50010],idx_min[50010];
void Init(){
	for(int ii=1;ii<=N;ii++){
		idx_max[ii]=idx_min[ii]=num[ii];
		for(int i=1;i<Lowbit(ii);i<<=1){
			idx_max[ii]=MAX(idx_max[ii],idx_max[ii-i]);
			idx_min[ii]=MIN(idx_min[ii],idx_min[ii-i]);
		}
	}
}

int Query(int l,int r){
	int mmax=num[r],mmin=num[r];
	while(true){
		mmax=MAX(mmax,num[r]);
		mmin=MIN(mmin,num[r]);
		if(r==l) break;
		for(r-=1;r-l>=Lowbit(r);r-=Lowbit(r)){
			mmax=MAX(mmax,idx_max[r]);
			mmin=MIN(mmin,idx_min[r]);
		}
	}
	return mmax-mmin;
}

int main(){
	int &n=N,m;
	while(~scanf("%d%d",&n,&m)){
		for(int i=1;i<=n;i++){
			scanf("%d",&num[i]);
		}
		Init();
		for(int i=0;i<m;i++){
			int l,r;
			scanf("%d%d",&l,&r);
			printf("%d\n",Query(l,r));
		}
	}
}