#include<bits/stdc++.h>
#define ll long long
#define N (int)2e5+5
using namespace std;
ll res,len,n,m,an,cnt0[N],cnt1[N],a[N],v[N],pos[N],ans[N];
struct Query{
	int id,L,R;
}q[N];
int read(){
	char c=getchar();
	int sum=0;
	while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9'){
		sum=sum*10+c-'0';
		c=getchar();
	}
	return sum;
}
bool cmp(Query x,Query y){
	return (pos[x.L]^pos[y.L])?(x.L<y.L):((pos[x.L]&1)?(x.R>y.R):(x.R<y.R));
}
int main(){
	n=read();
	len=sqrt(n);
	for(int i=1;i<=n;++i) v[i]=a[i]=read(),pos[i]=(i-1)/len+1;
	sort(a+1,a+1+n);
	an=unique(a+1,a+1+n)-a-1;
	for(int i=1;i<=n;++i) v[i]=lower_bound(a+1,a+1+an,v[i])-a,cnt0[v[i]]=INT_MAX,cnt1[v[i]]=INT_MIN;
	m=read();
	for(int i=1;i<=m;++i) q[i].L=read(),q[i].R=read(),q[i].id=i;
	sort(q+1,q+1+m,cmp);
	for(int i,j,k=1;k<=m;++k){
		if(pos[q[k].L]^pos[q[k-1].L]) res=0,i=pos[q[k].L]*len,j=i-1,memset(cnt0,0x3f3f3f,sizeof(cnt0)),memset(cnt1,0,sizeof(cnt1));
		if(pos[q[k].L]==pos[q[k].R]){
			int cnt2[N],cnt3[N],res1=0;
			memset(cnt2,0x3f3f3f,sizeof(cnt2));
			for(int c=q[k].L;c<=q[k].R;++c){
				cnt2[v[i]]=min(cnt2[v[i]],i);
				cnt3[v[i]]=max(cnt2[v[i]],i);
				res1=max(res1,cnt3[v[i]]-cnt2[v[i]]);
			}
			ans[q[k].id]=res1;
			continue;
		}
		while(j<q[k].R) cnt1[v[++j]]=j,cnt0[v[j]]=min(cnt0[v[j]],(ll)j),res=max(res,cnt1[v[j]]-cnt0[v[j]]);
		int tmp=i,tp=res;
		while(i>q[k].L) cnt0[v[--i]]=i,cnt1[v[i]]=max(cnt1[v[i]],(ll)i),res=max(res,cnt1[v[i]]-cnt0[v[i]]);
		ans[q[k].id]=res;
		while(i<tmp) cnt0[v[i]]=INT_MAX,cnt1[v[i]]=(cnt1[v[i]]==i?INT_MIN:i),++i;
		res=tp;
	}
	for(int i=1;i<=m;++i) printf("%d\n",ans[i]);
	return 0;
}