rt

#include<bits/stdc++.h>
#define _rep(i,a,b) for(int i=(a);i<=(b);i++)
#define _antirep(i,a,b) for(int i=(a);i>=(b);i--) 
#define In(x) freopen(x".in","r",stdin)
#define Out(x) freopen(x".out","w",stdout)
#define File(x) (In(x),Out(x))
#define sz(s) (int)(s.size())
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC optimize(3,"Ofast","inline")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
//#define int LL
using namespace std;
typedef long long LL;
typedef double db;
inline void write(int x);
inline int read();
const int N=2e5+5;
int n,m,bs,bn;
int a[N],b[N],c[N];
int L[N],R[N];
int cnt,tmp[N];
int lst[N],ans[N];
struct query
{
	int l,r,id;
}q[N];
bool cmp(query A,query B)
{
	if(b[A.l]!=b[B.l]) return b[A.l]<b[B.l];
	return A.r<B.r;
}
int calc(int l,int r)
{
	int res=0;
	_rep(i,l,r) lst[a[l]]=0;
	_rep(i,l,r)
	{
		if(!lst[a[i]]) lst[a[i]]=i;
		else res=max(res,i-lst[a[i]]);
	}
	return res;
}
signed main()
{        
	n=read();bs=sqrt(n);
	_rep(i,1,n) a[i]=read(),c[i]=a[i];
	_rep(i,1,n) b[i]=(i-1)/bs+1;bn=b[n];
	sort(c+1,c+n+1);
	int nn=unique(c+1,c+n+1)-c-1;
	_rep(i,1,n) a[i]=lower_bound(c+1,c+nn+1,a[i])-c;
	m=read();
	_rep(i,1,m)
	{
		q[i].l=read(),q[i].r=read();
		q[i].id=i;
	}
	sort(q+1,q+m+1,cmp);
	int i=1;
	_rep(j,1,bn)
	{
		int br=min(n,j*bs),l=br+1,r=l-1,res=0;
		cnt=0;
		for(;b[q[i].l]==j;++i)
		{
			if(b[q[i].r]==j)
			{
				ans[q[i].id]=calc(q[i].l,q[i].r);
				continue;
			}
			while(r<q[i].r)
			{
				++r;
				R[a[r]]=r;
				if(!L[a[r]]) L[a[r]]=r,tmp[++cnt]=a[r];
				res=max(res,r-L[a[r]]);
			}
			int tp=res;
			while(l>q[i].l)
			{
				--l; 
				if(!R[a[l]]) R[a[l]]=l;
				else res=max(res,R[a[l]]-l);
			}
			ans[q[i].id]=res;
			while(l<=br)
			{
				if(R[a[l]]==l) R[a[l]]=0;
				++l;
			}
			res=tp;
		}
		_rep(k,1,cnt) L[tmp[k]]=R[tmp[k]]=0;
	}
	_rep(k,1,m) write(ans[k]),putchar('\n');
	return 0;
}
inline void write(int x){
	if(x<0)putchar('-'),x=-x;
	static int sta[35];int top=0;
	do{sta[top++]=x%10,x/=10;}while(x);
	while(top)putchar(sta[--top]+48);}
inline int read(){
	int x=0,w=1;char ch=0;
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')
	{x=((x<<1)+(x<<3))+(ch-'0');ch=getchar();}
	return x*w;}