#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
struct RMQ{
	int N;
	int maxx[50020][30],minn[50020][30];
	void inin()
	  {
	  	for(int i=1;i<=N;i++)
	  	 scanf("%d",&maxx[i][0]);
	  	memcpy(minn,maxx,sizeof(maxx));
	  }
	void aa()
	{
		for(int i=1;(1<<i)<=N;i++)
		 for(int j=1;j+(1<<i)-1<=N;j++)
		   {
		   	 maxx[j][i]=max(maxx[j+(1<<i-1)][i-1],maxx[j][i-1]);
		   	 minn[j][i]=min(minn[j+(1<<i-1)][i-1],minn[j][i-1]);
		   }
	}
	void Query(int a,int b,int x,int y)
	{
	    int Max=0,Min=0;
		for(int i=0;(1<<(i+1)<=b-a+1);i++)
		 {
		 	Max=max(maxx[a][i],maxx[b-(1<<i)+1][i]);
		 	Min=min(minn[a][i],minn[b-(1<<i)+1][i]);
		 }
		x=Max;
		y=Min;
	}
	
}RMQ1;
int main()
{
	freopen("lineup.in","r",stdin);
	freopen("lineup.out","w",stdout);
    int Q;
	scanf("%d%d",&RMQ1.N,&Q);
	RMQ1.inin();
	RMQ1.aa();
	int l,r;
	for(int t=1;t<=Q;t++)
	  {
	  	scanf("%d%d",&l,&r);
	  	int x=0;
	  	int y=(1<<30);
	  	RMQ1.Query(l,r,x,y);
	  	cout<<x-y<<endl;
	  }
	  
	return 0;
}