#include <bits/stdc++.h>
using namespace std;
int a[100050];
int dpmax[180050][1050];
int dpmin[180050][1050];
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0) , cout.tie(0);
	int n=read(),m=read();
	for(int i=1;i<=n;i++)
		a[i]=read(),dpmax[i][0]=dpmin[i][0]=a[i];
	int len=1;
	for(int mi=1;len<=n;mi++)
	{
		len=1<<mi;
		for(int i=1;i-len+1<=n;i++)
		{
			int j=i+len-1;
			dpmax[i][mi]=max(dpmax[i][mi-1],dpmax[j-(1<<(mi-1))+1][mi-1]);	
			dpmin[i][mi]=min(dpmin[i][mi-1],dpmin[j-(1<<(mi-1))+1][mi-1]);	
		}	
	}
	while(m--)
	{
		int l=read(),r=read();
		int x=floor(log2((r-l)+1));
		cout<<max(dpmax[l][x],dpmax[r-(1<<x)+1][x])-min(dpmin[l][x],dpmin[r-(1<<x)+1][x])<<endl;
	}
	return 0;
}