#include<bits/stdc++.h>
using namespace std;
int a[200010],len,xh[200010],anss[200010],mn[200010],mx[200010],mx2[200010];
struct lj {
	int l,r,id;
}q[200010];
bool cmp(lj a,lj b) {
	if(xh[a.l]==xh[b.l]) return a.r<b.r;
	return xh[a.l]<xh[b.l];
}
int n,m,ch[200010];
signed main() {
	cin>>n;
	len=sqrt(n);
	for(int i=1;i<=n;i++) {
		scanf("%d",&ch[i]);
		xh[i]=(i-1)/len+1;
		a[i]=ch[i];
	}
	sort(ch+1,ch+n+1);
	int nn=unique(ch+1,ch+n+1)-ch-1;
	for(int i=1;i<=n;i++)
	    a[i]=lower_bound(ch+1,ch+nn+1,a[i])-ch;
	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);
	int l=0,r=0,ans,la=-1;     
	for(int i=1;i<=m;i++) {
		if(xh[q[i].l]==xh[q[i].r]) {
			ans=0;
			for(int j=q[i].l;j<=q[i].r;j++) mn[a[j]]=0;
			for(int j=q[i].l;j<=q[i].r;j++) {
				if(mn[a[j]]==0) mn[a[j]]=j;
				ans=max(ans,j-mn[a[j]]);
			}
			for(int j=q[i].l;j<=q[i].r;j++) mn[a[j]]=0;
			anss[q[i].id]=ans;
			continue ;
		}
		if(xh[q[i].l]!=la) {
			for(int j=l;j<=r;j++) mn[a[j]]=mx[a[j]]=0;
			l=min(xh[q[i].l]*len,n),r=l-1,ans=0,la=xh[q[i].l];
	    }
	    while(r+1<=q[i].r) {
	    	r++;
	    	if(mn[a[r]]==0) mn[a[r]]=r;
	    	mx[a[r]]=r;
	    	ans=max(ans,r-mn[a[r]]);
	   // 	cout<<l<<" "<<r<<" "<<ans<<q[i].id<<"\n";
		}
		int nl=l,jl=0;
		while(l-1>=q[i].l) {
			l--;
			if(mx2[a[l]]==0) mx2[a[l]]=l;
			jl=max(jl,max(mx[a[l]],mx2[a[l]])-l);
		}
		while(l+1<=nl) {
			l++;
			mx2[a[l]]=0;
		}
		anss[q[i].id]=max(ans,jl);
	}
	for(int i=1;i<=m;i++) printf("%d\n",anss[i]);
	return 0;
}