#include <bits/stdc++.h>

#define pb push_back
#define f first
#define s second
#define pii pair<int, int>
#define mp make_pair
 
using namespace std;
 
const string name = "pq",
             in_file = name + ".in",
             out_file = name + ".out";
 
ifstream fin(in_file);
ofstream fout(out_file);
 
const int MAX = 1e5 + 1;

struct Query {
	int lefty;
	int righty;
	int position;

	Query() {
		Query(0, 0, 0);
	}

	Query(int lefty, int righty, int position) {
		this->lefty = lefty;
		this->righty = righty;
		this->position = position;
	}
};

bool operator< (const Query& a, const Query& b) {
	return tie(a.lefty, a.righty) < tie(b.lefty, b.righty);
}

int n, q;
int segment_tree[4 * MAX], v[MAX], next_one[MAX], last[MAX], sol[MAX];
Query queries[MAX];

void update(int current, int left_bound, int right_bound, int position, int cost) {
	if (left_bound == position && right_bound == position) {
		segment_tree[current] = cost;
		return;
	}

	int mid = (left_bound + right_bound) / 2;
	int left_child = current * 2, right_child = left_child + 1;

	if (position <= mid) {
		update(left_child, left_bound, mid, position, cost);
	}

	if (mid < position) {
		update(right_child, mid + 1, right_bound, position, cost);
	}

	segment_tree[current] = max(segment_tree[left_child], segment_tree[right_child]);
}

int getMax(int current, int left_bound, int right_bound, Query& query) {
	if (left_bound >= query.lefty && right_bound <= query.righty) {
		return segment_tree[current];
	}

	int mid = (left_bound + right_bound) / 2; 
	int left_child = current * 2, right_child = left_child + 1;

	int maxx = -1;
	if (query.lefty <= mid) {
		maxx = max(maxx, getMax(left_child, left_bound, mid, query));
	}

	if (mid < query.righty) {
		maxx = max(maxx, getMax(right_child, mid + 1, right_bound, query));
	}

	return maxx;
}

int main() {
	fin >> n >> q;
	for (int i = 1; i <= n; i++) {
		fin >> v[i];
	}

	for (int i = 0; i < q; i++) {
		fin >> queries[i].lefty >> queries[i].righty;
		queries[i].position = i;
	}

	sort(queries, queries + q);

	for (int i = 1; i <= n; i++) {
		last[i] = next_one[i] = -1;
	}

	for (int i = 1; i < 4 * MAX; i++) {
		segment_tree[i] = -1;
	}

	int current_right = 1, current_left = 1;
	for (int i = 0; i < q; i++) {
		while (current_right <= queries[i].righty) {
			update(1, 1, n, current_right, last[v[current_right]] == -1 ? -1 : current_right - last[v[current_right]]);
			if (last[v[current_right]] != -1) {
				next_one[last[v[current_right]]] = current_right;
			} 
			last[v[current_right]] = current_right;
			current_right++;
		}

		while (current_left < queries[i].lefty) {
			if (next_one[current_left] != -1) {
				update(1, 1, n, next_one[current_left], -1);
			}
			current_left++;
		}

		sol[queries[i].position] = getMax(1, 1, n, queries[i]);
	}

	for (int i = 0; i < q; i++) {
		fout << sol[i] << '\n';
	}

	return 0;
}