#include <iostream>
using namespace std;
int madp[50001][17],midp[50001][17],a[50001];
void RMQmax(int n){
	 int i,j;
	 for(i=1;i<=n;i++)
	   madp[i][0]=a[i];
     for(int f=1,s=1;s<=n;s=(1<<f++))
        for(int i=1;i+s <= n;i++)
            madp[i][f]=max(madp[i][f-1],madp[i+s][f-1]);
}
int askmax(int light,int right){
	if(light>right )return -1;
	int d=right-light+1;
	int f;
	for(f=0;(1<<f)<=d;f++);
	f--;
	return max(madp[light][f],madp[right-(1<<f)+1][f]);
}
void RMQmin(int n){
	 int i,j;
	 for(i=1;i<=n;i++)
	   midp[i][0]=a[i];
     for(int f=1,s=1;s<=n;s=(1<<f++))
        for(int i=1;i+s <= n;i++)
            midp[i][f]=min(midp[i][f-1],midp[i+s][f-1]);
}
int askmin(int light,int right){
	if(light>right )return -1;
	int d=right-light+1;
	int f;
	for(f=0;(1<<f)<=d;f++);
	f--;
	return min(midp[light][f],midp[right-(1<<f)+1][f]);
}
int main(){
	int i,j,n,m,x,y;
	while(cin >> n >> m){
        for(i=1;i<=n;i++)
   		   scanf("%d",&a[i]);
        RMQmax(n);
        RMQmin(n);
        for(i=1;i<=m;i++){
           scanf("%d%d",&x,&y);
           printf("%d\n", askmax(x,y)-askmin(x,y));
        }
	}
}