#include<iostream>
#include<cstdio>
using namespace std;
int Max_num,Min_num;
int A[50000][20];
int B[50000][20];
int n,q,l,r;
void Query(int L,int R){
	int k=0;
	while((1<<(k+1))<=R-L+1) k++;
	Max_num=max(B[L][k],B[R-(1<<k)+1][k]);
	Min_num=min(A[L][k],A[R-(1<<k)+1][k]);
	}
int main(){
	freopen("lineup.in","r",stdin);
	freopen("lineup.out","w",stdout);
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++) scanf("%d",&A[i][0]);
	memcpy(B,A,sizeof(A));
    for(int j=1;(1<<j)<=n;j++)
	for(int i=1;i+(1<<j)-1<=n;i++){
		A[i][j]=min(A[i+(1<<(j-1))][j-1],A[i][j-1]);
		B[i][j]=max(B[i+(1<<(j-1))][j-1],B[i][j-1]);
	}
	for(int i=1;i<=q;i++){
		scanf("%d%d",&l,&r);
		Query(l,r);
		printf("%d\n",Max_num-Min_num);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}