#include <stdio.h>
#include <string.h>
#define MAX_N 70000
#include <algorithm>
using namespace std;
struct Node
{
	int w,max,min;
}s[MAX_N*2];
void Build(int L,int R,int root)
{
	if(L==R)
	{
		scanf("%d",&s[root].w);
		s[root].max=s[root].w;
		s[root].min=s[root].w;
		return ;
	}
	int mid=(L+R)/2;
	Build(L,mid,root*2);
	Build(mid+1,R,root*2+1);
	s[root].max=max(s[root*2].max,s[root*2+1].max);
	s[root].min=min(s[root*2].min,s[root*2+1].min);
}
//int Search_max(int L,int R,int root,int x,int y)
//{此种查找方法错误，但是做其它线段树的时候，用这种方法没有问题
//	if(x<=L && y>=R)
//		return s[root].max;
//	if(x>R || y<L)
//		return -1;
//	else
//	{
//		int mid=(L+R)/2;
//		return max(Search_max(L,mid,root*2,x,y),Search_max(mid+1,R,root*2+1,x,y));
//	}
//}
int Search_max(int L,int R,int root,int x,int y)
{
	if(x<=L && y>=R)
		return s[root].max;
	int mid=(L+R)/2;
	if(y<=mid)
		return Search_max(L,mid,root*2,x,y);
	else if(x>mid)
		return Search_max(mid+1,R,root*2+1,x,y);
	else
		return max(Search_max(L,mid,root*2,x,y),Search_max(mid+1,R,root*2+1,x,y));
}
int Search_min(int L,int R,int root,int x,int y)
{
	if(x<=L && y>=R)
		return s[root].min;
	int mid=(L+R)/2;
	if(y<=mid)
		return Search_min(L,mid,root*2,x,y);
	else if(x>mid)
		return Search_min(mid+1,R,root*2+1,x,y);
	else
		return min(Search_min(L,mid,root*2,x,y),Search_min(mid+1,R,root*2+1,x,y));
}
int main()
{
	int n,m,x,y;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		Build(1,n,1);
		while(m--)
		{
			scanf("%d%d",&x,&y);
			int ans1=Search_max(1,n,1,x,y);
			int ans2=Search_min(1,n,1,x,y);
			printf("%d\n",ans1-ans2);
		}
	}
	return 0;
}