#include <bits/stdc++.h>
using namespace std;
const int N=1e6;
int f[N][20],g[N][20],a[N],n,m,l,r; //f:最大值,g:最小值
//f[x][y]代表[x,x+(1<<y)-1]区间的最大值
void st()
{
	for (int i=1;i<=n;i++) f[i][0]=a[i];
	for (int j=1;j<=19;j++)
	  for (int i=1;i<=n;i++)
	     f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
	for (int j=1;j<=19;j++)
	  for (int i=1;i<=n;i++)
	     g[i][j]=min(g[i][j-1],g[i+(1<<(j-1))][j-1]); 
}
int main()
{
	cin>>n>>m;
	for (int i=1;i<=n;i++) cin>>a[i];
	st();
	while (m--)
	{
		cin>>l>>r;
		int t=log2(r-l+1);
		cout<<max(f[l][t],f[r-(1<<t)+1][t])-min(g[l][t],g[r-(1<<t)+1][t])<<"\n"; 
    }
    return 0;
}