#include<bits/stdc++.h>
using namespace std;
int read()
{
	char c;
	int r=0,f=1;
	c=getchar();
	while((c<'0'||c>'9')&&c!='-')
	c=getchar();
	if(c=='-')
	{
	f=-1;
    c=getchar();
	}
	while(c>='0'&&c<='9')
	{
	r=r*10+c-'0';
    c=getchar();
	}
	return r*f;
}
int h[100000],dp1[100000][100],dp2[100000][100];
int main()
{   
    memset(dp2,0x3f,sizeof(dp2));
    int n=read(),q=read();
    for(int i=1;i<=n;i++)
    h[i]=read();
    for(int i=1;i<=n;i++)
    {
	dp1[i][0]=h[i];
    dp2[i][0]=h[i];
	}
	for(int j=1;j<=log2(n);j++)
    for(int i=1;i<=n;i++)
    {
	dp1[i][j]=max(dp1[i][j-1],dp1[i+(1<<j-1)][j-1]);
    dp2[i][j]=min(dp2[i][j-1],dp2[i+(1<<j-1)][j-1]);
	}
    for(int i=1;i<=q;i++)
    {
    	int a=read(),b=read();
    	int maxn,minn;
    	int len=log2(b-a+1);
    	maxn=max(dp1[a][len],dp1[b-len][len]);
    	minn=min(dp2[a][len],dp2[b-len][len]);
    	cout<<maxn-minn<<endl;
	}
}