#include<bits/stdc++.h>
using namespace std;
int n,t,stmin[22][500005],stmax[22][500005];
int main(){
	cin>>n>>t;
	for(int i=1;i<=n;i++){
		scanf("%d",&stmin[0][i]);
		stmax[0][i]=stmin[0][i];
	}
	cout<<endl;
	for(int i=1;i<=21;i++){
		for(int j=1;j+(1<<i)-1<=n;j++){
			stmin[i][j]=min(stmin[i-1][j],stmin[i-1][j+(1<<(i-1))]);
			stmax[i][j]=max(stmax[i-1][j],stmax[i-1][j+(1<<(i-1))]);
			cout<<stmax[i][j]<<" "<<stmin[i][j]<<endl;
		}
		cout<<endl;
	}
	cout<<endl;
	cout<<endl;
	for(int i=1;i<=t;i++){
		int a=0,b=0;
		scanf("%d%d",&a,&b);
		int lo=log2(a-b+1);
		int mmin=min(stmin[lo][a],stmin[lo][b-(1<<lo)+1]);
		int mmax=max(stmax[lo][a],stmax[lo][b-(1<<lo)+1]);
		printf("%d\n",mmax-mmin);
	}
	return 0;
}