#include<iostream>
#include<cstdio>
#include<vector>
#define N 2000000
#define M 2097152
using namespace std;
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
struct node
{
	int num,data,nxt;
};
node edge[N+1];
int n,q,len,head[N+1],a[N+1],pv[N+1],nt[N+1],lg[N+1],ans[N+1],dque[N+1],top,lst[N+1],ST[N+1][21];
void add(int x,int d1,int d2)
{
	edge[++len]=(node){d1,d2,head[x]},head[x]=len;
    return;
}
int get_minn(int l,int r)
{
	int lw=lg[r-l+1];
	return min(ST[l][lw],ST[r-(1<<lw)+1][lw]);
}
struct seg
{
	struct node
	{
		int minn,lazy;
	};
	node tree[(M<<1)+1];
	void build(int k,int l,int r)
	{
		tree[k].minn=-r+1;
		if (l==r) return;
		int mid=(l+r)>>1;
		build(k<<1,l,mid),build(k<<1|1,mid+1,r);
		return;
	}
	void push_up(int k)
	{
		tree[k].minn=min(tree[k<<1].minn,tree[k<<1|1].minn);
		return;
	}
	void spread(int k)
	{
		if (tree[k].lazy)
		{
			tree[k<<1].minn+=tree[k].lazy,tree[k<<1].lazy+=tree[k].lazy;
			tree[k<<1|1].minn+=tree[k].lazy,tree[k<<1|1].lazy+=tree[k].lazy;
			tree[k].lazy=0;
		}
		return;	
	}
	void add(int k,int L,int R,int l,int r,int d)
	{
		if (l>r) return;
		if (L==l&&R==r)
		{
			tree[k].minn+=d,tree[k].lazy+=d;
			return;
		}
		spread(k);
		int mid=(L+R)>>1;
		if (r<=mid) add(k<<1,L,mid,l,r,d);
		else if (l>=mid+1) add(k<<1|1,mid+1,R,l,r,d);
		else add(k<<1,L,mid,l,mid,d),add(k<<1|1,mid+1,R,mid+1,r,d);
		push_up(k);
		return;
	}
	int query(int k,int L,int R,int l,int r)
	{
		if (L==l&&R==r) return tree[k].minn;
		spread(k);
		int mid=(L+R)>>1;
		if (r<=mid) return query(k<<1,L,mid,l,r);
		else if (l>=mid+1) return query(k<<1|1,mid+1,R,l,r);
		else return min(query(k<<1,L,mid,l,mid),query(k<<1|1,mid+1,R,mid+1,r));
	}
};
seg T;
int main()
{
	int l,r,ps,ps2,ps3;
	n=read(),T.build(1,1,n);
	for (int i=2;i<=N;++i) lg[i]=lg[i>>1]+1;
	for (int i=1;i<=n;++i) a[i]=read(),lst[i]=n+1;
	for (int i=n;i>=1;--i) nt[i]=lst[a[i]],lst[a[i]]=i;
	for (int i=1;i<=n;++i) lst[i]=0;
	for (int i=1;i<=n;++i) pv[i]=lst[a[i]],lst[a[i]]=i;
	for (int i=1;i<=n;++i) ST[i][0]=pv[i];
	for (int i=1;i<=lg[n];++i)
		for (int j=1;j+(1<<i)-1<=n;++j)
			ST[j][i]=min(ST[j][i-1],ST[j+(1<<(i-1))][i-1]);
	q=read(),dque[0]=n;
	for (int i=1;i<=q;++i) l=read(),r=read(),add(l,i,r);
	for (int i=n;i>=1;--i)
	{
		while (top&&nt[dque[top]]<=nt[i]) T.add(1,1,n,dque[top]+1,dque[top-1],-nt[dque[top]]),top--;
		dque[++top]=i,T.add(1,1,n,dque[top]+1,dque[top-1],nt[dque[top]]);
		for (int j=head[i];j>0;j=edge[j].nxt)
		{
			ps=i-1;
			for (int k=lg[edge[j].data-i];k>=0;--k)
				if (ps+(1<<k)<edge[j].data&&get_minn(ps+(1<<k)+1,edge[j].data)<i)
					ps+=(1<<k);
			ps++,ps2=top+1;
			for (int k=lg[top];k>=0;--k)
				if (ps2-(1<<k)>=1&&nt[dque[ps2-(1<<k)]]<=edge[j].data)
					ps2-=(1<<k);
			ps2=dque[ps2-1],ps3=top+1;
			for (int k=lg[edge[j].data-i];k>=0;--k)
				if (ps3-(1<<k)>=1&&nt[dque[ps3-(1<<k)]]<ps)
					ps3-=(1<<k);
			ps3=dque[ps3-1],ans[edge[j].num]=ps-ps3+1;
			if (ps3+1<=ps2) ans[edge[j].num]=min(ans[edge[j].num],T.query(1,1,n,ps3+1,ps2));
		}
	}
	for (int i=1;i<=q;++i) printf("%d\n",ans[i]);
	return 0;
}