#include<bits/stdc++.h>
using namespace std;
int st[100001][13],st1[50001][13];
void read(int &x){
	x=0;
	int f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	x*=f;
}
int main(){
	int n,m;
	read(n);
	read(m);
	for(int i=1;i<=n;i++){
		read(st[i][0]);
		st1[i][0]=st[i][0];
	}
	for(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]);
			st1[i][j]=min(st1[i][j-1],st1[i+(1<<j-1)][j-1]);
		}
	}
	while(m){
		m--;
		int x,y;
		read(x);
		read(y);
		printf("%d\n",max(st[x][int(log2(y-x+1))],st[y-(1<<int(log2(y-x+1)))+1][int(log2(y-x+1))])-min(st1[x][int(log2(y-x+1))],st1[y-(1<<int(log2(y-x+1)))+1][int(log2(y-x+1))]));
	}
	return 0;
}