// 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;

#define VMAX 16//131072
#define BASE (VMAX)

int treeval[2*VMAX];
int treestart[2*VMAX];
int treeend[2*VMAX];


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) / 2;
	gen_tree(2 * p, start, mid);
	gen_tree(2 * p + 1, mid + 1, end);
}

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

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

int main(int argc, char* argv[])
{
	FILE *fi, *fo;
	int i, j;
	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);
	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));
	gen_tree(1, 0, VMAX - 1);
	idx = (int *)malloc(100000 * sizeof(int));
	for (i = 0; i < 100000; i++)
		idx[i] = -1;
	for (i = 0; i < N; i++)
		fscanf(fi, "%d ", A + i);
	for (i = 0; i < Q; i++)
	{
		fscanf(fi, "%d %d", &(q[i].a), &(q[i].b));
		q[i].a -= 1;
		q[i].b -= 1;
		q[i].idx = i;
	}

	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++)
		fprintf(fo, "%d\n", q[i].max);

	fclose(fi);
	fclose(fo);
	return 0;
}