#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MB=1<<20;
struct FastIO{
	char ib[MB+100],*p,*q;
	char ob[MB+100],*r,stk[128];
	int tp;
	FastIO(){p=q=ib,r=ob,tp=0;}
	~FastIO(){fwrite(ob,1,r-ob,stdout);}
	char read_char(){
		if(p==q){
			p=ib,q=ib+fread(ib,1,MB,stdin);
			if(p==q)return 0;
		}
		return *p++;
	}
	template<typename T>
	void read_int(T& x){
		char c=read_char(),l=0;
		for(x=0;!isdigit(c);c=read_char())l=c;
		for(;isdigit(c);c=read_char())x=x*10-'0'+c;
		if(l=='-')x=-x;
	}
	void write_char(char c){
		if(r-ob==MB)r=ob,fwrite(ob,1,MB,stdout);
		*r++=c;
	}
	template<typename T>
	void write_int(T x){
		if(x<0)write_char('-'),x=-x;
		do stk[++tp]=x%10+'0';
		while(x/=10);
		while(tp)write_char(stk[tp--]);
	}
}IO;
const int N=2e6+5;
int n,q,a[N];
int las[N];
int tag[N<<2],minn[N<<2];
int ans[N];
#define lc k<<1
#define rc k<<1|1
#define ls lc,l,mid
#define rs rc,mid+1,r
void pushdown(int k,int l,int r){
	int mid=l+r>>1;
	if(tag[k]){
		tag[lc]=tag[rc]=tag[k];
		minn[lc]=tag[k]-mid;
		minn[rc]=tag[k]-r;
		tag[k]=0;
	}
}
void pushup(int k){minn[k]=min(minn[lc],minn[rc]);}
void change(int k,int l,int r,int x,int y,int d){
	if(x<=l&&r<=y){
		tag[k]=d+1;
		minn[k]=(d-r+1);
		return ;
	}
	int mid=l+r>>1;
	pushdown(k,l,r);
	if(x<=mid) change(ls,x,y,d);
	if(mid<y) change(rs,x,y,d);
	pushup(k);
}
int ask(int k,int l,int r,int x,int y){
	if(x<=l&&r<=y) return minn[k];
	int mid=l+r>>1;
	pushdown(k,l,r);
	if(x<=mid&&mid<y) return min(ask(ls,x,y),ask(rs,x,y));
	if(x<=mid) return ask(ls,x,y);
	return ask(rs,x,y);
}
int fa[N];
int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
struct node{int l,id;};
vector<node>b[N];
int main(){
	IO.read_int(n);
	for(int i=1;i<=n;i++) IO.read_int(a[i]);
	for(int i=1;i<=n;i++) fa[i]=i;
	IO.read_int(q);
	for(int i=1,x,y;i<=q;i++){
		IO.read_int(x);
		IO.read_int(y);
		b[y].push_back(node{x,i});
	}
	for(int i=1,x;i<=n;i++){
		x=las[a[i]];
		if(x) fa[x]=x+1;
		change(1,1,n,x+1,i,i);
		for(node e:b[i]) ans[e.id]=ask(1,1,n,e.l,find(e.l));
		las[a[i]]=i;
	}
	for(int i=1;i<=q;i++){
		IO.write_int(ans[i]);
		IO.write_char('\n'); 
	}
	return 0;
}