#include <stdio.h>
#include <stdlib.h>

typedef struct pont {
	int ertek;
	struct pont *kov;
}PONT;

PONT *tomb[100001];
int sor[100001];

void beszur(int n, PONT **point) {
	if (!(*point)) {
		*point = (PONT *)malloc(sizeof(PONT));
		(*point)->ertek = n;
		(*point)->kov = NULL;
	}
	else {
		PONT *it = *point;
		while (it->kov != NULL) {
			it = it->kov;
		}
		it->kov = (PONT *)malloc(sizeof(PONT));
		it->kov->ertek = n;
		it->kov->kov = NULL;
	}
	return;
}

int main() {
	int N, Q, i, j, a, b, maxi, maxi1, k;
	PONT *it;
	freopen("pq.in", "r", stdin);
	freopen("pq.out", "w", stdout);
	scanf("%d%d", &N, &Q);
	for (i = 0; i < N; ++i) {
		scanf("%d", &sor[i]);
		beszur(i, &tomb[sor[i]]);
	}
	/*
	for (i = 0; i < N; ++i) {
		printf("%d ", sor[i]);
	}
	printf("\n");
	for (PONT *it = tomb[1];it != NULL; it = it->kov) {
		printf("%d ", it->ertek);
	}*/
	for (i = 0; i < Q; ++i) {
		scanf("%d%d", &a, &b);
		maxi = -1;
		for (j = a; j <= b; ++j) {
			maxi1 = -1;
			for (it = tomb[sor[j - 1]], k = tomb[sor[j-1]]->ertek; it != NULL && it->ertek <= b - 1; it = it->kov) {
				if (it != NULL && it != tomb[sor[j-1]] && k >= a-1 && it->ertek >= a - 1 && maxi1 < it->ertek - k) {
					maxi1 = (it->ertek) - k;
				}
				if (it->ertek >= a-1 && it->ertek <= b-1)
					k = it->ertek;
			}
			if (maxi < maxi1) {
				maxi = maxi1;
			}
		}
		printf("%d\n", maxi);
	}
	return 0;
}