// Template v2
#define pb push_back
#define mp make_pair
#define det(a,b,c,d)  (a*d-b*c)
#define first x
#define second y
#define lsb(x) x & -x
#define l(x) (x<<1)
#define r(x) ((x<<1)|1)
#define PI   3.14159265358979323846
#include<cstdio>
#include<vector>
#include<iomanip>
#include<map>
#include<set>
#include<algorithm>
#include<string.h>
#include<stack>
#include<unordered_map>
#include <bitset>
using namespace std;
typedef long long LL;
typedef long double LD;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<double, double> PKK;
// primes less than 100
const int PRIM[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}; const int CMAX = 100069;
const int MOD = 1000000007;
const int POW1 = 31;
const int MOD2 = 10429;
const int POW2 = 13;
const int P = 73;
const int NMAX = 105069;
const double EPS = 1e-12;
const int INF16 = 320000;
const int INF = 0x3F3F3F3F;
const LL INF64 = LL(1e18);
const int dx[]={-1,1,0,0};
const int dy[]={0,0,1,-1};

struct interval{
	int x, y, id;
	friend bool operator<(const interval &l, const interval &r)
	{
		return l.x<r.x || (l.x==r.x && l.y<r.y);
	}
};

int le[NMAX], ri[NMAX];
interval q[NMAX];
int A[NMAX], used[NMAX], last[NMAX],rsint[NMAX];
int rs;
int T[4*NMAX];

void update(int n, int l, int r, int poz, int val)
{
	if(l==r)
	{
		T[n]=val;
		return;
	}
	int pivot=(l+r)>>1;
	if(poz<=pivot)
		update(l(n), l, pivot, poz, val);
	else
		update(r(n), pivot+1, r, poz, val);
	T[n]=max(T[l(n)], T[r(n)]);
}

void query(int n, int l, int r, int ql, int qr)
{
	if(ql<=l && r<=qr)
	{
		rs=max(rs, T[n]);
		return;
	}
	int pivot=(l+r)>>1;
	if(ql<=pivot)
		query(l(n), l, pivot, ql, qr);
	if(qr>pivot)
		query(r(n), pivot+1, r, ql, qr);
}
int n,m;
void read()
{
	scanf("%i %i", &n, &m);
	for(int i=1; i<=n; ++i){
		scanf("%i", &A[i]);
	}

	for(int i=1; i<=m; ++i){
		scanf("%i %i", &q[i].x, &q[i].y);
		q[i].id=i;
	}

	sort(q+1, q+1+m);

	memset(T, -1, sizeof(T));

	for(int i=1; i<=n; ++i)
	{
		if(last[A[i]])
			le[i]=last[A[i]];
		if(le[i])
			update(1, 1, n, i, i-le[i]);
		last[A[i]]=i;
	}
	memset(last, 0, sizeof(last));
	for(int i=n; i>=1; i--)
	{
		if(last[A[i]])
			ri[i]=last[A[i]];
		last[A[i]]=i;
	}

	int l=1;
	
	for(int i=1; i<=m; ++i)
	{
		while(l<q[i].x)
		{
			if(ri[l])
				update(1, 1, n, ri[l], -1);
			l++;
		}
		rs=-1;

		query(1, 1, n, q[i].x, q[i].y);
		rsint[q[i].id]=rs;
	}
	for(int i=1; i<=m; ++i)
		printf("%i \n", rsint[i]);
}
 
int main()
{
	freopen("pq.in", "rt", stdin);
	freopen("pq.out", "wt", stdout);
    read();
    return 0;
}