#include<bits/stdc++.h>
using namespace std;
int n,q,a[50020],stmax[30][50020],stmin[30][50020];
void init(int n){
	for(int i=1;i<=n;i++){
		stmax[i][0]=a[i];
		stmin[i][0]=a[i];
	} 	
	for(int j=1;(1<<j)<=n;j++){
		for(int i=1;i+(1<<j)-1<=n;i++){
			stmax[i][j]=max(stmax[i][j-1],stmax[i+(1<<(j-1))][j-1]);
			stmin[i][j]=min(stmin[i][j-1],stmin[i+(1<<(j-1))][j-1]);
		}
	}
}
int getm(int l,int r){
	int k=log2(r-l+1);
	int maxx=max(stmax[l][k],stmax[r-(1<<k)+1][k]);
	int minn=min(stmin[l][k],stmin[r-(1<<k)+1][k]);
	return maxx-minn;
}

int main()
{
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	init(n);
	while(q--){
		int x,y;
		scanf("%d%d",&x,&y);
		printf("%d\n",getm(x,y));
	}
	return 0;
}