#include<bits/stdc++.h>
using namespace std;

const int N=2e5+10;

int n,q;

int fn[N][24],fx[N][24];

int main()
{
	cin>>n>>q;
	for(int i=1;i<=n;i++)
	{
		cin>>fx[i][0];
		fn[i][0]=fx[i][0];
	}
	for(int j=1;(j)<=log(n);j++)
	{
		for(int i=1;i+(1<<j)-1<=n;i++)
		{
			fn[i][j]=min(fn[i][j-1],fn[i+(1<<j-1)][j-1]);
			fx[i][j]=max(fx[i][j-1],fx[i+(1<<j-1)][j-1]);
		}
	}
	while(q--)
	{
		int l,r;
		cin>>l>>r;
		int k=log(r-l+1);
		cout<<max(fx[l][k],fx[r-(1<<k)+1][k])-min(fn[l][k],fn[r-(1<<k)+1][k])<<endl;
	}
	return 0;
}