RT,只有 pts#1 有十分。

//By: Luogu@wangdemao(308854)
#include <iostream>
#define ull unsigned long long
#define int long long 

using namespace std;

const int INF=0x3f3f3f3f;

struct Node
{
	int u,Min,Max;
};
Node a[5000000];
int n;
int h[5000000];

inline int lc(int u) 
{
	return 1<<u;
}
inline int rc(int u)
{
	return (1<<u)+1;
}

void PushUp(int u)
{
	a[u].Max=max(a[lc(u)].Max,a[rc(u)].Max);
	a[u].Min=min(a[lc(u)].Min,a[rc(u)].Min);
}

void MakeTree(int u,int l,int r)
{
	if(l==r)
	{
		a[u].Max=h[l];
		a[u].Min=h[l];
		
		return ;
	}
	
	int mid=(l+r)/2;
		
	MakeTree(lc(u),l,mid);
	MakeTree(rc(u),mid+1,r);
	
	PushUp(u);
	
	//cout<<u<<" "<<l<<' '<<r<<' '<<a[u].Min<<' '<<a[u].Max<<" \n\n";
	
	return ;
}

int QueryMin(int u,int l,int r,int ql,int qr)
{
	if(ql<=l && r<=qr)
	{
		return a[u].Min;
	}
	
	int ans=INF;
	int mid=(l+r)/2;
	
	if(ql<=mid)
	{
		ans=min(ans,QueryMin(lc(u),l,mid,ql,qr));
	}
	if(qr>mid)
	{
		ans=min(ans,QueryMin(rc(u),mid+1,r,ql,qr));
	}
	
	return ans;
}

int QueryMax(int u,int l,int r,int ql,int qr)
{
	if(ql<=l && r<=qr)
	{
		return a[u].Max;
	}
	
	int ans=-0;
	int mid=(l+r)/2;
	
	if(ql<=mid)
	{
		ans=max(ans,QueryMax(lc(u),l,mid,ql,qr));
	}
	if(qr>mid)
	{
		ans=max(ans,QueryMax(rc(u),mid+1,r,ql,qr));
	}
	
	return ans;
}

signed main()
{
	int q;
	
	cin>>n>>q;
	
	for(int i=1;i<=n;i++)
		cin>>h[i];
	
	MakeTree(1,1,n);
	
	while(q--)
	{
		int a,b;
		
		cin>>a>>b;
		
		cout<<QueryMax(1,1,n,a,b)-QueryMin(1,1,n,a,b)<<endl;
	}
	
	return 0;
}