#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

const int SIZE = 100005;

struct input_thing {
	int pos;
	int val;
};

struct input_interval {
	int left;
	int len;
};

struct query_interval {
	int left;
	int len;
	int pos;
};

struct solution {
	int pos;
	int len;
};

int N;
input_thing input[SIZE];
input_interval input_intervals[SIZE];
int input_intervals_len;
query_interval query_intervals[SIZE];
int query_intervals_len;
vector<query_interval> curr_query_intervals;
vector<solution> solutions;

int cmp1(input_thing a, input_thing b) {
	if (a.val != b.val)
		return a.val < b.val;
	return a.pos < b.pos;
}

int cmp2(input_interval a, input_interval b) {
	//if (a.left != b.left)
	//	return a.left < b.left;
	return a.len > b.len;
}

int cmp3(query_interval a, query_interval b) {
	//if (a.len != b.len)
		return a.len > b.len;
	//return a.len > b.len;
}

int cmp4(solution a, solution b) {
	return a.pos < b.pos;
}

int main() {
	freopen("pq.in", "r", stdin);
	freopen("pq.out", "w", stdout);

	scanf("%d%d", &N, &query_intervals_len);
	for (int i = 1; i <= N; i++) {
		scanf("%d", &input[i].val);
		input[i].pos = i;
	}

	sort(input+1, input+N+1, cmp1);

	for (int i = 2; i <= N; i++) {
		if (input[i-1].val == input[i].val) {
			input_intervals[input_intervals_len].left = input[i-1].pos;
			input_intervals[input_intervals_len].len = input[i].pos - input[i-1].pos;
			input_intervals_len++;
		}
	}

	sort(input_intervals, input_intervals+input_intervals_len, cmp2);

	for (int i = 0, right; i < query_intervals_len; i++) {
		scanf("%d %d\n", &query_intervals[i].left, &right);
		query_intervals[i].len = right - query_intervals[i].left;
		query_intervals[i].pos = i;
	}

	sort(query_intervals, query_intervals+query_intervals_len, cmp3);
	
	int i, j, k;
	for (i = 0, j = 0; i < input_intervals_len; i++) {
		while (j < query_intervals_len) {
			if (query_intervals[j].len < input_intervals[i].len)
				break;
			curr_query_intervals.push_back(query_intervals[j]);
			j++;
		}

		for (k = 0; k < curr_query_intervals.size(); k++) {
			if (curr_query_intervals[k].left <= input_intervals[i].left) {
				if (input_intervals[i].left + input_intervals[i].len <= curr_query_intervals[k].left + curr_query_intervals[k].len) {
					solution sol;
					sol.len = input_intervals[i].len;
					sol.pos = curr_query_intervals[k].pos;
					solutions.push_back(sol);
					curr_query_intervals[k] = curr_query_intervals[curr_query_intervals.size()-1];
					curr_query_intervals.pop_back();
					k--;
				}
			}
		}
	}

	//printf("--> j=%d, %d \n", j, query_intervals_len);
	for (; j < query_intervals_len; j++) {
		solution sol;
		sol.len = -1;
		sol.pos = query_intervals[j].pos;
		//printf("--> %d %d %d\n", query_intervals[j].left, query_intervals[j].len, query_intervals[j].pos);
		solutions.push_back(sol);

	}

	for (k = 0; k < curr_query_intervals.size(); k++) {
		solution sol;
		sol.len = -1;
		sol.pos = curr_query_intervals[k].pos;
		solutions.push_back(sol);
	}

	sort(solutions.begin(), solutions.end(), cmp4);

	for (int i = 0; i < solutions.size(); i++) {
		printf("%d\n", solutions[i].len);
	}

	/*
	for (int i = 0; i < input_intervals_len; i++) {
		printf("%d %d\n", input_intervals[i].left, input_intervals[i].left + input_intervals[i].len);
	}
	
	printf("\n\n");
	
	for (int i = 0; i < query_intervals_len; i++) {
		printf("%d %d\n", query_intervals[i].left, query_intervals[i].left + query_intervals[i].len);
	}
	*/
	
	return 0;
}