#include<bits/stdc++.h>
using namespace std;
struct node{
	int l,r,id;
}q[200005];
int n,m,cnt;
int a[200005],b[200005],bl,blo[200005],bn,ans[200005],clear[200005],las[200005],st[200005];
bool cmp(node x,node y){
	if(blo[x.l]==blo[y.l])return x.r<y.r;
	return x.l<y.l;
}
int calc(int l,int r){
	int last[200005]={},ans=0;
	for(int i=l;i<=r;i++){
		if(!last[a[i]])last[a[i]]=i;
		else ans=max(ans,i-last[a[i]]);
	}
	return ans;
}
int main(){
	scanf("%d",&n);
	bl=sqrt(n);
	for(int i=1;i<=n;i++){
		scanf("%d",(a+i));
		b[i]=a[i];
		blo[i]=(i-1)/bl+1;
	}
	bn=blo[n];
	sort(b+1,b+n+1);
	
	int len=unique(b+1,b+n+1)-b-1;
	for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+len+1,a[i])-b;
	cin>>m;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&q[i].l,&q[i].r);
		q[i].id=i;
	}
	sort(q+1,q+m+1,cmp);
//	for(int i=1;i<=m;i++){
//		cout<<q[i].l<<" "<<q[i].r<<endl;;
//	}
	for(int i=1,j=1;j<=bn;j++){
		int br=min(n,j*bl),l=br+1,r=l-1,sum=0;
		cnt=0;
		for(;blo[q[i].l]==j;i++){
			int ql=q[i].l,qr=q[i].r;
			if(blo[qr]==j){
				ans[q[i].id]=calc(ql,qr);
				continue;
			}
			while(r<qr){
				r++;
				las[a[r]]=r;
				if(!st[a[r]])st[a[r]]=r,clear[++cnt]=a[r];
				sum=max(r-st[a[r]],sum);
			}
			int tmp=sum;
			while(l>ql){
				l--;
				if(las[a[l]])sum=max(sum,las[a[l]]-l);
				else las[a[l]]=l;
			}
			ans[q[i].id]=sum;
			while(l<=br){
				if(las[a[l]]==l)las[a[l]]=0;
				l++;
			}
			sum=tmp;
		}
		for(int i=1;i<=cnt;i++)las[clear[i]]=st[clear[i]]=0;
	}
	for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
}