#include<cstdio>
#include<cmath>
#define max(a,b) (a>b?a:b)
#define min(a,b) (a>b?a:b)
using namespace std;
const int N=1e5+8e4+5;
int n,m,l,r,a[N][22],f[N][21];
int query(int l,int r){
    int k=log2(r-l+1),x=max(a[l][k],a[r-(1<<k)+1][k]),y=min(f[l][k],f[r-(1<<k)+1][k]);
    return x-y;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i) scanf("%d",&a[i][0]),f[i][0]=a[i][0];
	for(int j=1;j<=21;++j)
		for(int i=1;i+(1<<j)<=n+1;++i)
			a[i][j]=max(a[i][j-1],a[i+(1<<(j-1))][j-1]),f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
	while(m--){
		scanf("%d%d",&l,&r);
		printf("%d\n",query(l,r));
	}
	return 0;
}