#include <iostream>
#include <fstream>
#include <algorithm>
#define nmx 100005

using namespace std;
ifstream fin("pq.in");
ofstream fout("pq.out");

int n,q,i,j,nr,p;
int l[nmx],v[nmx],aib[nmx],z[nmx];
struct per
{	int x,y,d;
	bool operator<(const per &doi)const
	{	return x>doi.x;	 }
} u[nmx];

void add(int x,int c)
{
	for(;x<=n;x+=x&-x)
		if(aib[x]<c)
			aib[x]=c;
}
int query(int x)
{
	int mx=0;
	for(;x>0;x-=x&-x)
		if(aib[x]>mx)
			mx=aib[x];
	if(mx==0)	mx=-1;
	return mx;
}
int main() {
	
	fin>>n>>q;
	for(i=1;i<=n;i++)
		fin>>v[i];
	for(i=1;i<=q;i++)
		fin>>u[i].x>>u[i].y, u[i].d=i;
	sort(u+1,u+n+1);
	
	p=n;
	for(i=1;i<=q;i++)
	{
		for(;p>=u[i].x;p--)
		{
			if(l[v[p]])
				add(l[v[p]], l[v[p]]-p);
						
			l[v[p]]=p;
		}
		z[u[i].d]=query(u[i].y);
	}
	for(i=1;i<=q;i++)
		fout<<z[i]<<"\n";
}