#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mpr make_pair
#define fr first
#define sc second
#define rc(x) min(n,(x)*val)
#define lc(x) ((x)*val-val+1)
inline int read(){
	int res=0,f=1;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') {res=res*10+(c-'0');c=getchar();}
	return res*f;
}
const int N=2e5+5;
int n,m,a[N],block[N],val,ans,output[N],nxt[N];
struct node{
	int l,r,i;
}q[N];
bool comp(node o,node p){
	if (block[o.l]==block[p.l]) return o.r<p.r;
	return block[o.l]<block[p.l];
}
unordered_map<int,int>ml,mr,ml2,mr2;
int baoli(int l,int r){
	int res=0;
	for (int i=l;i<=r;i++){
		if (ml2[a[i]]==0) ml2[a[i]]=i;
		mr2[a[i]]=i;
	}
	for (int i=l;i<=r;i++){
		res=max(res,mr2[a[i]]-ml2[a[i]]);
		ml2[a[i]]=n+1,mr2[a[i]]=0;
	}
	return res;
}
void add(int x,int &s){
	ml[a[x]]=min(ml[a[x]],x),mr[a[x]]=max(mr[a[x]],x);
	s=max(s,mr[a[x]]-ml[a[x]]);
}
void del(int x){
	ml[a[x]]=nxt[x];
}
signed main(){
	n=read(),val=sqrt(n);
	for (int i=1;i<=n;i++){
		a[i]=read();
		nxt[ml[a[i]]]=i;
		ml[a[i]]=i;
		ml2[a[i]]=n+1;
		block[i]=(i-1)/val+1;
//		cout<<block[i]<<' ';
	}
	for (int i=1;i<=n;i++){
		ml[a[i]]=n+1;
	}
	m=read();
//	cout<<'\n';
	for (int i=1;i<=m;i++){
		int l=read(),r=read();
		q[i]={l,r,i};
	}
	sort(q+1,q+m+1,comp);
	int tl=1,tr=0,lst=0;
	for (int i=1;i<=m;i++){
		int l=q[i].l,r=q[i].r,I=q[i].i;
//		cout<<"oi: "<<l<<' '<<r<<' '<<I<<'\n';
		if (block[l]==block[r]){
			output[I]=baoli(l,r);
			continue;
		}
		if (block[lst]!=block[l]){
//			cout<<block[lst]<<' '<<block[l]<<" ok!\n";
			for (int i=tl;i<=tr;i++){
				ml[a[i]]=n+1;
				mr[a[i]]=0;
			}
			tl=rc(block[l])+1;
			tr=tl-1;
			ans=0;
		}
//		cout<<"fuck: "<<tl<<' '<<tr<<'\n';
		while (tr<r) add(++tr,ans);
//		cout<<"a: "<<ml[3]<<' '<<mr[3]<<'\n';
		int anss=ans;
		while (l<tl) add(--tl,anss);
		output[I]=anss;
//		cout<<"a: "<<ml[3]<<' '<<mr[3]<<'\n';
		while (tl<rc(block[l])+1) del(tl++);
		lst=q[i].l;
	}
	for (int i=1;i<=m;i++) cout<<output[i]<<'\n';
	return 0;
}
/*
12 2
15 9 3 15 9 3 3 8 16 9 3 17
2 5
2 2
*/

https://www.luogu.com.cn/record/152752706