#include<iostream>
#include<cstdio>
#include<climits>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#define peppery_chicken 200003
#define dingsc_my_grandson
using namespace std;
int n,m,mi[peppery_chicken][20]={0},ma[peppery_chicken][20]={0};
int RMQ(int x,int y,bool a){
	if(x>y) swap(x,y);
	int k=0;
	while((1<<(k+1))<=y-x+1) k++;
	if(a) return min(mi[x][k],mi[y-(1<<k)+1][k]);
	else return max(ma[x][k],ma[y-(1<<k)+1][k]);
}
void init(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>mi[i][0];
		ma[i][0]=mi[i][0];
	}
	for(int i=1;(1<<i)<=n;i++)
	{
		for(int j=1;j+(1<<i)-1<=n;j++)
		{
			mi[j][i]=min(mi[j][i-1],mi[j+(1<<(i-1))][i-1]);
			ma[j][i]=max(ma[j][i-1],ma[j+(1<<(i-1))][i-1]);
		}
	}
	int x,y;
	for(int i=1;i<=m;i++)
	{
		cin>>x>>y;
		cout<<RMQ(x,y,false)-RMQ(x,y,true)<<endl;
	}
}
int main(){
	freopen("lineup.in","r",stdin);
	freopen("lineup.out","w",stdout);
	init();
	return 0;
}