// pq.cpp : Defines the entry point for the console application.
//
#include <malloc.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct __segm
{
	int a, b;
	int idx;
	int max;
} Q_TYPE;

int q_comp(const void *a, const void *b)
{
	Q_TYPE *pa = (Q_TYPE *)a;
	Q_TYPE *pb = (Q_TYPE *)b;
	if (pa->b < pb->b)
		return -1;
	else if (pa->b > pb->b)
		return 1;
	else
	{
		if (pa->idx < pb->idx)
			return -1;
		else if (pa->idx > pb->idx)
			return 1;
		else
			return 0; // No way to get here!
	}
}

int idx_comp(const void *a, const void *b)
{
	Q_TYPE *pa = (Q_TYPE *)a;
	Q_TYPE *pb = (Q_TYPE *)b;
	if (pa->idx < pb->idx)
		return -1;
	else if (pa->idx > pb->idx)
		return 1;
	else
		return 0;
}

int N, Q;
int *A;
Q_TYPE *q;
int *idx;

int VMAX;
#define BASE (VMAX)

int *treeval;
int *treestart;
int *treeend;


void gen_tree(int p, int start, int end)
{
	treeval[p] = -1;
	treestart[p] = start;
	treeend[p] = end;
	if (start == end)
		return;

	int mid = (start + end)>>1;
	int p2 = p << 1;
	gen_tree(p2, start, mid);
	gen_tree(p2 + 1, mid + 1, end);
}

void propagate(int p, int v)
{
	if (treeval[p] < v)
	{
		treeval[p] = v;
		if (p!=1)
			propagate(p>>1, v);
	}
}

int getmax(int p, int s)
{
	if (s>treeend[p])
		return -1;
	if (s <= treestart[p])
		return treeval[p];
	int p2 = p << 1;
	int v1 = getmax(p2, s);
	int v2 = getmax(p2 + 1, s);
	if (v1 > v2)
		return v1;
	else
		return v2;
}

inline int getnum(char *buf, int *v, int *sz)
{
	char *b2 = buf;
	while (*sz > 0 && (*buf==' ' || *buf=='\n' || *buf == '\r'))
	{
		buf++;
		(*sz)--;
	}
	while (*sz>0 && (*buf>='0' && *buf<='9'))
	{
		buf++;
		(*sz)--;
	}
	*v = atoi(b2);
	return buf-b2;
}

int main(int argc, char* argv[])
{
	FILE *fi, *fo;
	int i;
	int iq;
	fi = fopen("pq.in", "r");
	fo = fopen("pq.out", "w");
	if (!fi)
	{
		printf("fi.in...\n");
		return -1;
	}
	fscanf(fi, "%d %d ", &N, &Q);
	i = 0;
	int tQ = Q;
	while (tQ)
	{
		tQ >>= 1;
		i++;
	}
	VMAX = 1 << i;
	A = (int *) malloc(N * sizeof(int));
	q = (Q_TYPE *) malloc(N * sizeof(Q_TYPE));
	treeval = (int *)malloc(2 * VMAX * sizeof(int));
	treestart = (int *)malloc(2 * VMAX * sizeof(int));
	treeend = (int *)malloc(2 * VMAX * sizeof(int));
	//char *bufi = (char *)malloc(2000000);
	//char *buf = bufi;
	int sz = 2000000;
	//fgets(buf, 2000000, fi);
	for (i = 0; i < N; i++)
	{
		//int l = getnum(buf, A + i, &sz);
		//buf += l;
		fscanf(fi, "%d", A + i);
	}
	//buf = bufi;
	//sz = fread(buf, 1, 2000000, fi);
	for (i = 0; i < Q; i++)
	{
		//int l = getnum(buf, &(q[i].a), &sz);
		//buf += l;
		//l = getnum(buf, &(q[i].b), &sz);
		//buf += l;
		fscanf(fi, "%d %d", &(q[i].a), &(q[i].b));
		q[i].a -= 1;
		q[i].b -= 1;
		q[i].idx = i;
	}
	gen_tree(1, 0, VMAX - 1);
	idx = (int *)malloc(100000 * sizeof(int));
	for (i = 0; i < 100000; i++)
		idx[i] = -1;
	
	qsort(q, Q, sizeof(Q_TYPE), q_comp);
	i = 0;
	iq = 0;
	while (i < N)
	{
		int v = A[i];
		if (idx[v] != -1)
		{
			int len = i - idx[v];
			if (len > 0)
			{
				propagate(BASE + idx[v], len);
			}
		}
		idx[v] = i;
		
		while (iq<Q && q[iq].b <= i)
		{
			q[iq].max = getmax(1, q[iq].a);
			iq++;
		}
		
		i++;
	}
//	qsort(q, Q, sizeof(Q_TYPE), idx_comp);
	for (i = 0; i < Q; i++)
		treeval[q[i].idx] = q[i].max;
	for (i = 0; i < Q; i++)
		fprintf(fo, "%d\n", treeval[i]);

	fclose(fi);
	fclose(fo);

	return 0;
}