#include<stdio.h>
#include<math.h>
static int v[50005], d[50005][20], d2[50005][20];

static int xmin(int a, int b){
	return (v[a] <= v[b]) ? a : b;
}

static int xmax(int a, int b){
	return (v[a] >= v[b]) ? a : b;
}

static int rmq(int a, int b){
	int k = log2(b-a+1);
#ifdef DEBUG
	fprintf(stderr, "rmq(%d, %d) -> k=%d\n", a, b, k);
#endif
	return xmin(d[a][k], d[b-(1<<k)+1][k]);
}

static int rmq2(int a, int b){
	int k = log2(b-a+1);
	return xmax(d2[a][k], d2[b-(1<<k)+1][k]);
}

int main(void){
#ifdef INFOARENA
	freopen("rmq.in","r",stdin);
	freopen("rmq.out","w",stdout);
#endif
	int n, q, i, j;
	scanf("%d %d", &n, &q);
	for(i=0;i<n;i++)
		scanf("%d", v+i);

	for(i=0;i<n;i++)
		d[i][0]=d2[i][0]=i;
	for(j=1;(1<<j)<=n;j++){
		for(i=0;i+(1<<j)-1<n;i++)
			d[i][j] = xmin(d[i][j-1], d[i+(1<<(j-1))][j-1]);
	}

	for(j=1;(1<<j)<=n;j++){
		for(i=0;i+(1<<j)-1<n;i++)
			d2[i][j] = xmax(d2[i][j-1], d2[i+(1<<(j-1))][j-1]);
	}

#ifdef DEBUG
	for(i=0;i<n;i++){
		for(j=0;(1<<j)<=n;j++)
			fprintf(stderr, "%d ", d[i][j]);
		fputs("\n", stderr);
	}
#endif
	
	while(q--){
		scanf("%d %d", &i, &j);

#ifdef INFOARENA
		if(i==j)
			printf("%d\n", v[i]);
		else
			printf("%d\n", v[rmq(i-1, j-1)]);
#else
		if(i==j)
			puts("0");
		else
			printf("%d\n", v[rmq2(i-1, j-1)] - v[rmq(i-1, j-1)]);
#endif
	}

	return 0;
}