#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int n,m;
int a[N],b[N];
int blocked[N],block[N];
int lp=1,rp,lst,lstb,st[N],ed[N],ed1[N];
int ans[N];
struct node{
	int l,r,lid,id;
}q[N];
bool cmp(node x,node y){return x.lid==y.lid?x.r<y.r:x.lid<y.lid;}
void move(int l,int r,int id){
	if(block[l]==block[r]){
		lst=0;
		for(int i=l;i<=r;i++) st[a[i]]=0;
		for(int i=l;i<=r;i++){
			if(!st[a[i]]) st[a[i]]=i;
			lst=max(lst,i-st[a[i]]);
		}
		for(int i=l;i<=r;i++) st[a[i]]=0;
		ans[id]=lst;
		return ;
	}
	int now=block[l];
	if(lstb!=now){
		lst=0;
		for(int i=l;i<=r;i++) st[a[i]]=ed[a[i]]=0;
		lp=blocked[now];rp=l-1;
		lstb=now;
	}
	while(rp<r){
		rp++;
		if(!st[a[rp]]) st[a[rp]]=rp;
		ed[a[rp]]=rp;
		lst=max(lst,rp-st[a[rp]]);
	}
	int p=lp,res=0;
	while(p>l){
		p--;
		if(!ed1[a[p]]) ed1[a[p]]=p;
		res=max(res,max(ed[a[p]],ed1[a[p]])-p);
	}
	while(p<lp) ed1[p]=0,p++;
	ans[id]=max(res,lst);
}
signed main(){
	scanf("%lld",&n);
	int len=sqrt(n);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]),b[i]=a[i],block[i]=(i-1)/len+1;
	scanf("%lld",&m);
	for(int i=1;i<=m;i++){
		scanf("%lld%lld",&q[i].l,&q[i].r);
		q[i].lid=(q[i].l-1)/len+1;
		q[i].id=i;
	}
	for(int i=1;i<=block[n];i++){
		if(i==block[n]) blocked[i]=n;
		else blocked[i]=i*len;
	}
	sort(q+1,q+m+1,cmp),sort(b+1,b+n+1);
	int num=unique(b+1,b+n+1)-b-1;
	for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+num+1,a[i])-b;
	for(int i=1;i<=m;i++) move(q[i].l,q[i].r,q[i].id);
	for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
	return 0;
}