#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>

using namespace std;

struct node
{
	int l,r,id;
}p[1000000];

int n,m,one,kl[1000000],kr[1000000],len=0;
int a[1000000],aaa[1000000],pos[1000000];
int ans[1000000]={};
int l[1000000]={},r[1000000]={};

inline int rd()
{
	int s=0;char x='x';
	while(x<'0'||x>'9')x=getchar();
	while(x>='0'&&x<='9'){s=s*10+(x^48);x=getchar();}
	return s;
}

inline bool cmp1(node x,node y){return pos[x.l]==pos[y.l]?x.r<y.r:x.l<y.l;}

inline void readd()
{
	int k;
	n=rd();
	for(int i=1;i<=n;i++)aaa[i]=a[i]=rd();
	sort(aaa+1,aaa+1+n);
	k=unique(aaa+1,aaa+1+n)-aaa-1;
	for(int i=1;i<=n;i++)a[i]=lower_bound(aaa+1,aaa+1+k,a[i])-aaa;
	m=rd();
	for(int i=1;i<=m;i++)
	{
		p[i].id=i;
		p[i].l=rd();
		p[i].r=rd();
	}
	
	//cout<<endl;
	
	one=sqrt(n);
	for(int i=1;i<=n;i++)
	{
		if(len*one<i)
		{
			len++;
			kl[len]=i;
		}
		pos[i]=len;
		//cout<<pos[i]<<' ';
		kr[len]=i;
	}
	sort(p+1,p+1+m,cmp1);
}

inline void calc(int u)
{
	int L[10000];
	for(int i=p[u].l;i<=p[u].r;i++)L[a[i]]=0;
	for(int i=p[u].l;i<=p[u].r;i++)
	{
		if(L[a[i]]&&i-L[a[i]]>ans[p[u].id])ans[p[u].id]=i-L[a[i]];
		L[a[i]]=i;
	}
}

inline void md()
{
	for(int i=1,j=1;j<=len;j++)
	{
		int lef=kr[j]+1,rig=kr[j],res=0;
		for(;pos[p[i].l]==j;i++)
		{
			if(pos[p[i].r]==j)
			{
				calc(i);
				continue;
			}
			
			while(rig<p[i].r)
			{
				rig++;
				if(l[a[rig]]==0)l[a[rig]]=rig;
				res=max(res,rig-l[a[rig]]);
				r[a[rig]]=rig;
			}
			
			ans[p[i].id]=res;
			
			while(lef>p[i].l)
			{
				lef--;
				if(r[a[lef]]==0)r[a[lef]]=lef;
				ans[p[i].id]=max(ans[p[i].id],r[a[lef]]-lef);
			}
			
			while(lef<kr[j]+1)
			{
				if(r[a[lef]]==lef)r[a[lef]]=0;
				lef++;
			}
		}
		for(int k=kl[j];k<=rig;k++)l[a[k]]=r[a[k]]=0;
	}
}

inline void print()
{
	for(int i=1;i<=m;i++)
		printf("%d\n",ans[i]);
}

int main()
{
	readd();
	md();
	print();
	return 0;
}