#include<bits/stdc++.h>
#define lowbit(x) x&(-x)
#define inf 0x7fffffff
#define int long long
using namespace std;
int n,q;
int h[50005]; 
int bitmax[50005],bitmin[50005];
void add(int k,int x)
{
	for(int i=k;i<=n;i+=lowbit(i))
		bitmax[i]=max(bitmax[i],x),bitmin[i]=min(bitmin[i],x);
	return ;
}
int ask(int l,int r)
{
	int maxx=-inf;
	int minn=inf;
	for(int i=r;i>l;i--)
	{
		for(;(i-lowbit(i))>l;i-=lowbit(i))
		{
			maxx=max(maxx,bitmax[i]);
			minn=min(minn,bitmin[i]);
		}
		maxx=max(maxx,h[i]);
		minn=min(minn,h[i]);
	}
	return maxx-minn;
}
main()
{
	cin>>n>>q;
	for(int i=1;i<=n;i++)
	{
		cin>>h[i];
		add(i,h[i]);
	}
	for(int i=1;i<=q;i++)
	{
		int l,r;
		cin>>l>>r;
		cout<<ask(l,r)<<"\n";
	}
	return 0;
}

TLE on #2 & #3