#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstring>
#include<deque>
#define itn int
#define coder goodboy
using namespace std;
typedef long long LL;typedef unsigned long long ULL;
int n;int m;
const int MAXN=50010;
const int MAXLOG=50;
int A[MAXN][MAXLOG];//min
int B[MAXN][MAXLOG];//max
void init(){
	scanf("%d%d",&n,&m);
	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]);
		}
    }
int Max_num,Min_num;
void Query(int L,int R){
	int k=0;
	Max_num=-1;Min_num=1000001;
	while((1<<(k+1))<=R-L+1) k++;
	Max_num=max(B[L][k],B[R-(1<<k)+1][k]);//cout<<Max_num<<endl;
	Min_num=min(A[L][k],A[R-(1<<k)+1][k]);//cout<<Min_num<<endl;
	printf("%d\n",Max_num-Min_num);
}
void deal(){
		//scanf("%d",&m);
		int temp1,temp2;
		for (int i=1;i<=m;i++){
			scanf("%d%d",&temp1,&temp2);
			Query(temp1,temp2);
		}
		return;
	}
int Main(){
	freopen("lineup.in","r",stdin);
	freopen("lineup.out","w",stdout);
	init();
	deal();
	return 0;
}
int main(){;}
int goodboy=Main();