#include<bits/stdc++.h>
using namespace std;
const int MAXN=200000;
int n,m,sq,sum,l=0,r=1,blo,a[MAXN+10],b[MAXN+10],bl[MAXN+10],L[MAXN+10],last[MAXN+10],last2[MAXN+10],ans[MAXN+10],bao[MAXN+10];
struct node{ int l,r,id; }p[MAXN+10];
inline bool cmp(node x,node y){
	if(bl[x.l]!=bl[y.l]) return x.l<y.l;
	return x.r<y.r;
}//fc C:\Users\cqbz\Desktop\out.out C:\Users\cqbz\Desktop\P5806_2.out
int main(){
//	freopen("P5906_2.in","r",stdin);
//	freopen("out.out","w",stdout);
	scanf("%d",&n),sq=sqrt(n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),bl[i]=(i-1)/sq+1,b[i]=a[i]; blo=bl[n];
	sort(b+1,b+1+n); int size=unique(b+1,b+1+n)-b-1;
	for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+size,a[i])-b;
	scanf("%d",&m);
	for(int i=1;i<=m;i++) scanf("%d%d",&p[i].l,&p[i].r),p[i].id=i;
	sort(p+1,p+1+m,cmp);
	for(int i=1;i<=blo;i++) L[i]=i*sq+1; L[blo]=min(L[blo],n);
	int j=1;
	for(int i=1;i<=blo;i++){
		l=L[i],r=L[i]-1,sum=0;
		for(int k=1;k<=n;k++) last[k]=last2[k]=0;
		for(;bl[p[j].l]==i;j++){
			if(bl[p[j].l]==bl[p[j].r]){
				vector<int> cle; int s=0;
				for(int k=p[j].l;k<=p[j].r;k++){
					if(!bao[a[k]]) bao[a[k]]=k,cle.push_back(a[k]);
					else s=max(s,k-bao[a[k]]),bao[a[k]]=k;
				}
				ans[p[j].id]=s;
				for(int k=0;k<cle.size();k++) bao[cle[k]]=0;
				continue;
			}
			while(p[j].r>r) { ++r; if(!last[a[r]]) last[a[r]]=r; else sum=max(sum,r-last[a[r]]); last2[a[r]]=r; }
			int now=0;
			vector<int> cle;
			while(l>p[j].l){ --l; if(!last2[a[l]]) last2[a[l]]=l,cle.push_back(a[l]); else now=max(now,last2[a[l]]-l); }
			//for(int i=0;i<cle.size();i++) last2[cle[i]]=0;
			ans[p[j].id]=max(now,sum),l=L[i];
		}
	}
	for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
	return 0;
}