#include <stdio.h>
#define len 50010
typedef struct node
{
	int lchild;
	int rchild;
	int max;
	int min;
}Node;
Node a[len*6];
int data[len];
int MAX(int a,int b)
{
	return a>b?a:b;
}
int MIN(int a,int b)
{
	return a>b?b:a;
}
int bulitmax(int s,int e,int step)
{
	int mid;
    a[step].lchild=s;
	a[step].rchild=e;
	if(s==e)
	{
		a[step].max=data[s];
		return data[s];
	}
	else
	{
		mid=(s+e)>>1;
		a[step].max=MAX(bulitmax(s,mid,2*step),bulitmax(mid+1,e,2*step+1));
		return a[step].max;
	}
}
int bulitmin(int s,int e,int step)
{
	int mid;
	if(s==e)
	{
		a[step].min=data[s];
		return data[s];
	}
	else
	{
		mid=(s+e)>>1;
		a[step].min=MIN(bulitmin(s,mid,2*step),bulitmin(mid+1,e,2*step+1));
		return a[step].min;
	}
}
void print(int s,int e,int step)
{
	int mid;
	if(s==e)
	{
		printf("%d %d %d %d %d\n",step,a[step].lchild,a[step].rchild,a[step].max,a[step].min);
		return ;
	}
	else
	{
		mid=(s+e)>>1;
		print(s,mid,2*step);
		print(mid+1,e,2*step+1);
		printf("%d %d %d %d %d\n",step,a[step].lchild,a[step].rchild,a[step].max,a[step].min);
	}
}
int querymax(int s,int e,int step)
{
	int mid;
	if(a[step].lchild==s&&a[step].rchild==e)
		return a[step].max;
	else
	{
		mid=(a[step].lchild+a[step].rchild)>>1;
		if(s>mid)
		return querymax(s,e,2*step+1);
		else
		if(e<=mid)
		return querymax(s,e,2*step);
		else
		return MAX(querymax(s,mid,2*step),querymax(mid+1,e,2*step+1));
	}
}
int querymin(int s,int e,int step)
{
	int mid;
	if(a[step].lchild==s&&a[step].rchild==e)
		return a[step].min;
	else
	{
		mid=(a[step].lchild+a[step].rchild)>>1;
		if(s>mid)
			return querymin(s,e,2*step+1);
		else
			if(e<=mid)
				return querymin(s,e,2*step);
			else
				return MIN(querymin(s,mid,2*step),querymin(mid+1,e,2*step+1));
	}
}
int main()
{
	int n,m,i,s,e;
	while(scanf("%d %d",&n,&m)!=EOF)
	{
		for(i=1;i<=n;i++)
		scanf("%d",&data[i]);
        bulitmax(1,n,1);
		bulitmin(1,n,1);
	//	print(1,n,1);
		while(m--)
		{
		scanf("%d %d",&s,&e);
		printf("%d\n",querymax(s,e,1)-querymin(s,e,1));
		}
	}
	return 1;
}