rt

#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline ll read(){
	ll x=0;
	short f=1;
	char c=getchar();
	while(c>57||c<48){
		if(c==45) f=-1;
		c=getchar();
	}
	while(c<58&&c>47){
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}
inline void write(ll x){
	if(x<0ll) putchar(45),x=~x+1;
	if(x>9ll) write(x/10);
	putchar(x%10|48);
}
map<int,int>mp;
int n=read(),m,len=sqrt(n),a[2000005],ans[2000005];
#define bl(i) ((i-1)/len+1)
struct node{
	int l,r,id;
}q[2000005];
int operator<(node a,node b){
	return bl(a.l)==bl(b.l)?a.r<b.r:a.l<b.l;
}
int lmn[2000005],rmx[2000005],prmx[2000005],nans,st[2000005],tp;
int ft(int l,int r){
	int ret=0;
	for(int i=l;i<=r;i++) lmn[a[i]]=lmn[a[i]]?lmn[a[i]]:i,ret=max(ret,i-lmn[a[i]]);
	for(int i=l;i<=r;i++) lmn[a[i]]=0;
	return ret;
}
int main(){
	int tot=0;
	for(int i=1;i<=n;i++){
		a[i]=read();
		if(!mp[a[i]]) mp[a[i]]=++tot;
		a[i]=mp[a[i]];
	}
	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+m+1);
	for(int i=1;i<=m;){
		int bn=bl(q[i].l);
		int r=bn*len,l=r+1;
		nans=0;
		for(;bl(q[i].l)==bn;i++){
			int ql=q[i].l,qr=q[i].r;
			if(bl(qr)==bn) ans[q[i].id]=ft(ql,qr);
			while(r<qr){
				r++;
				if(!rmx[a[r]]) st[++tp]=a[r];
				lmn[a[r]]=lmn[a[r]]?lmn[a[r]]:r,rmx[a[r]]=r;
				nans=max(nans,r-lmn[a[r]]);
			}
			int pans=nans;
			while(l>ql){
				l--;
				prmx[a[l]]=prmx[a[l]]?prmx[a[l]]:l;
				nans=max(nans,max(rmx[a[l]],prmx[a[l]])-l);
			}
			ans[q[i].id]=nans;
			nans=pans;
			while(l<=bn*len){
				prmx[a[l]]=0;
				l++;
			}
		}
		while(tp) lmn[st[tp]]=rmx[st[tp--]]=0;
	}
	for(int i=1;i<=m;i++){
		printf("%d\n",ans[i]);
	}
}