#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
using namespace std;
const int MAXN=2333;
const int MAXLOG=30;
int A[MAXN][MAXLOG];//min
int B[MAXN][MAXLOG];//max
int main()
{
	freopen("lineup.in","r",stdin);
	freopen("lineup.out","w",stdout);
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) 
	  scanf("%d\n",&A[i][0]);
	memcpy(B,A,sizeof(A));
	for(int j=1;(1<<j)<=n;j++)
	  for(int i=1;i+(1<<j)-1<=n;i++)
	  {
	      A[i][j]=min(A[i+(1<<(j-1))][j-1],A[i][j-1]);
		  B[i][j]=max(B[i+(1<<(j-1))][j-1],B[i][j-1]);
	  }
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		int Max_num,Min_num;
	    int k=0;
	    while((1<<(k+1))<=y-x+1) 
	      k++;
	    Max_num=max(B[x][k],B[y-(1<<k)+1][k]);
	    Min_num=min(A[x][k],A[y-(1<<k)+1][k]);
	    int p=Max_num-Min_num;
		printf("%d\n",p);
    }
    return 0;
}