#include <vector>
#include <algorithm>
#include <cstring>
#include <fstream>
#include <queue>

using namespace std;

ifstream fin("pq.in");
ofstream fout("pq.out");

const int dim = 100005;

int n, m;

int v[dim], lst[dim], nxt[dim], sol[dim];

int evC;
struct Ev {
	int l, r, i;
} ev[2 * dim];

int aint[4 * dim];

void update(int cur, int l, int r, int pos, int val) {

	if (l == r) {
		aint[cur] = val;
		return;
	}

	int m = (l + r) / 2;
	if (m >= pos)
		update(2 * cur, l, m, pos, val);
	else
		update(2 * cur + 1, m + 1, r, pos, val);

	aint[cur] = max(aint[2 * cur], aint[2 * cur + 1]);

}

int query(int cur, int l, int r, int ql, int qr) {

	if (ql <= l && r <= qr) {
		return aint[cur];
	}

	int q1 = -1, q2 = -1, m = (l + r) / 2;

	if (ql <= m)
		q1 = query(2 * cur, l, m, ql, qr);
	if (m < qr)
		q2 = query(2 * cur + 1, m + 1, r, ql, qr);

	return max(q1, q2);

}

inline bool  cmp(const Ev &a, const Ev &b) {

	return (a.l == b.l ? a.i > b.i : a.l < b.l);

}

int main() {

	fin >> n >> m;
	for (int i = 1; i <= n; ++i)
		fin >> v[i];

	for (int i = 1; i <= n; ++i)
		nxt[lst[v[i]]] = i, lst[v[i]] = i;

	memset(aint, -1, sizeof aint);
	for (int i = 1; i <= n; ++i) {
		if (nxt[i] == 0)
			continue;
		ev[++evC].l = i;
		ev[evC].r = nxt[i];
		ev[evC].i = 0;
		update(1, 1, n, nxt[i], nxt[i] - i);
	}

	for (int i = 1; i <= m; ++i) {
		int a, b;
		fin >> a >> b;
		++evC;
		ev[evC].i = i;
		ev[evC].l = a;
		ev[evC].r = b;
	}

	sort(ev + 1, ev + evC + 1, cmp);

	for (int i = 1, j = 1; i <= n; ++i) {

		while (j <= evC && ev[j].l == i) {

			if (ev[j].i > 0)
				sol[ev[j].i] = query(1, 1, n, ev[j].l, ev[j].r);
			else
				update(1, 1, n, ev[j].r, -1);

			++j;

		}

	}

	for (int i = 1; i <= m; ++i)
		fout << sol[i] << '\n';

	return 0;

}

//Trust me, I'm the Doctor!