#include<iostream>
using namespace std;
int x[100000],fmax,fmin;
struct itree
{
	int left,right;
	int imax,imin;
	itree *lc,*rc;
};
struct pp
{
	int imax,imin;
};
pp btree(itree *h)
{
	int tmid;
	pp j,k;
	tmid=(h->left+h->right)/2;
	if(h->left==h->right)
	{
		h->imax=x[h->left];
		h->imin=h->imax;
		j.imax=h->imax;
		j.imin=h->imin;
		return j;
	}
	
	itree *q,*p;
	q=new itree;
	p=new itree;
	h->lc=q;
	h->rc=p;
	q->lc=0;
	q->rc=0;
	p->lc=0;
	p->rc=0;

	q->left=h->left;
	q->right=tmid;
	p->left=tmid+1;
	p->right=h->right;

	j=btree(q);
	k=btree(p);

	j.imax=j.imax>k.imax?j.imax:k.imax;
	j.imin=j.imin<k.imin?j.imin:k.imax;
	h->imax=j.imax;
	h->imin=j.imin;
	return j;
}
void qtree(itree *h,int ll,int rr)
{
	int tmid;
	tmid=(h->left+h->right)/2;
	if(ll==h->left && rr==h->right)
	{
		if(fmax<h->imax || fmax==-1) fmax=h->imax;
		if(fmin>h->imin || fmin==-1) fmin=h->imin;
		return ;
	}
	if(rr<=tmid) qtree(h->lc,ll,rr);
	else if(ll>tmid) qtree(h->rc,ll,rr);
	else
	{
		qtree(h->lc,ll,tmid);
		qtree(h->rc,tmid+1,rr);
	}
}

void bl(itree *h)
{
	cout<<h->left<<"--"<<h->right<<":"<<h->imax<<"  "<<h->imin<<endl;
	if(h->lc) bl(h->lc);
	if(h->rc) bl(h->rc);
}
int main()
{
	itree *h;
	int i,j,k,n,q;
	scanf("%d%d",&n,&q);
	for(i=1;i<=n;++i)
	{
		scanf("%d",&x[i]);
	}
	h=new itree;
	h->left=1;
	h->right=n;
	btree(h);
//	bl(h);
	for(i=0;i<q;++i)
	{
		fmax=-1;
		fmin=-1;
		scanf("%d%d",&j,&k);
		qtree(h,j,k);
		cout<<fmax-fmin<<endl;	
	}
	
	return 0;
}