You are given sequence *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> and *m* queries *l*<sub class="lower-index">*j*</sub>, *r*<sub class="lower-index">*j*</sub> (1 ≤ *l*<sub class="lower-index">*j*</sub> ≤ *r*<sub class="lower-index">*j*</sub> ≤ *n*). For each query you need to print the minimum distance between such pair of elements *a*<sub class="lower-index">*x*</sub> and *a*<sub class="lower-index">*y*</sub> (*x* ≠ *y*), that:
 -  both indexes of the elements lie within range [*l*<sub class="lower-index">*j*</sub>, *r*<sub class="lower-index">*j*</sub>], that is, *l*<sub class="lower-index">*j*</sub> ≤ *x*, *y* ≤ *r*<sub class="lower-index">*j*</sub>; -  the values of the elements are equal, that is *a*<sub class="lower-index">*x*</sub> = *a*<sub class="lower-index">*y*</sub>. 
The text above understands distance as |*x* - *y*|.
The first line of the input contains a pair of integers *n*, *m* (1 ≤ *n*, *m* ≤ 5·10<sup class="upper-index">5</sup>) — the length of the sequence and the number of queries, correspondingly. 

The second line contains the sequence of integers *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> ( - 10<sup class="upper-index">9</sup> ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>). 

Next *m* lines contain the queries, one per line. Each query is given by a pair of numbers *l*<sub class="lower-index">*j*</sub>, *r*<sub class="lower-index">*j*</sub> (1 ≤ *l*<sub class="lower-index">*j*</sub> ≤ *r*<sub class="lower-index">*j*</sub> ≤ *n*) — the indexes of the query range limits.
# LUOGU_RID: 94159977
#include <bits/stdc++.h>
#define inf 500005
using namespace std;
int n,m,cnt,now=1,a[500005],b[500005],pre[500005],ans[500005];
inline int read ()
{
	int x=0,flag=1;
	char ch=getchar();
	while (ch<'0' || ch>'9') { if (ch=='-') flag=-flag; ch=getchar(); }
	while (ch>='0' && ch<='9') { x=x*10+ch-'0';ch=getchar(); }
	return x*flag;
}
struct query
{
	int i,l,r;
	query _read (int k)
	{
		i=k;
		l=read(); r=read();
		return *this;
	}
} q[500005];
inline bool operator< (query a,query b)
{
	return a.l<b.l;
}
struct Tree_Min
{
	int val[2000005];
	void build (int i,int l,int r,int* a)
	{
		if (l>r) return;
		if (l==r) { val[i]=a[l]; return; }
		int mid=(l+r)>>1;
		build (i<<1,l,mid,a);
		build (i<<1|1,mid+1,r,a);
		val[i]=min(val[i<<1],val[i<<1|1]);
	}
	void add (int i,int l,int r,int x)
	{
		if (l>r || x<l || x>r) return;
		if (l==r)
		{
			if (x==l) val[i]=inf;
			return;
		}
		int mid=(l+r)>>1;
		add (i<<1,l,mid,x);
		add (i<<1|1,mid+1,r,x);
		val[i]=min(val[i<<1],val[i<<1|1]);
	}
	int query (int i,int l,int r,int x,int y)
	{
		if (l>r || y<l || x>r) return inf;
		if (x<=l && y>=r) return val[i];
		int mid=(l+r)>>1;
		return min(query(i<<1,l,mid,x,y),query(i<<1|1,mid+1,r,x,y));
	}
} tree;
map<int,int> mp;
int main ()
{
	n=read(); m=read();
	for (int i=1;i<=n;i++)
	{
		a[i]=/*b[i]=*/read();
		if (mp.count(a[i])) pre[i]=i-mp[a[i]]; 
		else pre[i]=inf;
		mp[a[i]]=i;
	}
	tree.build (1,1,n,pre);
//	sort (b+1,b+n+1);
//	cnt=unique(b+1,b+n+1)-b;
	for (int i=1;i<=m;i++) q[i]._read(i);
	sort (q+1,q+m+1);
	for (int i=1;i<=m;i++)
	{
		for (int j=q[i].l;j<=q[i].r;j++)
			if (j-pre[j]<q[i].l)
				tree.add (1,1,n,j); 
		ans[q[i].i]=tree.query (1,1,n,q[i].l,q[i].r);
	}
	for (int i=1;i<=m;i++)
		printf ("%d\n",ans[i]==inf?-1:ans[i]);
}