#include<bits/stdc++.h>
using namespace std;
const int N=(int)5e4+10;
int h[N],f[N][30][2],n,q;
void ST_create(){
	for(int i=1;i<=n;i++){
		f[i][0][0]=f[i][0][1]=h[i];
	}
	for(int j=1;(1<<j)<=n;j++){
		for(int i=1;i<=n-(1<<j)+1;i++){
			f[i][j][0]=max(f[i][j-1][0],f[i+1<<(j-1)][j-1][0]);
			f[i][j][1]=min(f[i][j-1][1],f[i+1<<(j-1)][j-1][1]);
		}
	}
}
int ST_query(int a,int b){
	int k=log2(b-a+1);
	return max(f[a][k][0],f[b-(1<<k)+1][k][0])-min(f[a][k][1],f[b-(1<<k)+1][k][1]);
}
int main(){
	for(int i=1;i<=N-10;i++){
		for(int j=0;j<=29;j++){
			f[i][j][1]=0x3f3f3f3f;
		}
	}
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++) scanf("%d",&h[i]);
	ST_create();
	while(q--){
		int a,b;
		scanf("%d%d",&a,&b);
		printf("%d\n",ST_query(a,b));
	}
	return 0;
}