#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,inf=1061109567;
template <typename T> inline void chkmin(T &x,T y) {x=x<y?x:y;}
template <typename T> inline void chkmax(T &x,T y) {x=x>y?x:y;}
int n,m,a[N],b[N],mn[N],mn2[N],res,ans[N],blo[N],bl,nw=1,len;
struct query{int l,r,id;}q[N];
inline void add(int x) {chkmin(mn[a[x]],x),chkmax(res,x-mn[a[x]]);}
inline int calc(int l,int r) 
{
	int ret=0;for(int i=l;i<=r;i++) mn2[a[i]]=inf;
	for(int i=l;i<=r;i++) chkmin(mn2[a[i]],i),chkmax(ret,i-mn2[a[i]]);
	return ret;
}
inline void solve(int pos)
{
	res=0;int qr=min(n,pos*bl),pr=qr;memset(mn,0x3f,sizeof(mn));
	for(;blo[q[nw].l]==pos;nw++)
	{
		if(blo[q[nw].l]==blo[q[nw].r]) {ans[q[nw].id]=calc(q[nw].l,q[nw].r);continue;}
		while(pr<q[nw].r) add(++pr);int lst=res;
		for(int i=q[nw].l;i<=qr;i++) mn2[a[i]]=mn[a[i]];
		for(int i=q[nw].l;i<=qr;i++) add(i);
		ans[q[nw].id]=res;
		for(int i=q[nw].l;i<=qr;i++) mn[a[i]]=mn2[a[i]];
		res=lst;
	}
}

int main()
{
	scanf("%d",&n);bl=sqrt(n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i],blo[i]=(i-1)/bl+1;
	sort(b+1,b+1+n);len=unique(b+1,b+1+n)-b-1;
	for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+len+1,a[i])-b;
	scanf("%d",&m);for(int i=1;i<=m;i++) scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;
	sort(q+1,q+1+m,[&](query &a,query &b){return blo[a.l]==blo[b.l]?a.r<b.r:a.l<b.l;});
	for(int i=1;i<=blo[n];i++) solve(i);
	for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
	return 0;
}