RT

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
const ll MAXN=3e5+5;
ll n,q,a[MAXN],tmp[MAXN];
ll blen;
struct block{
	ll l,r;
}b[MAXN];
ll cnt,b_id[MAXN];
ll ans[MAXN];
set<ll> pos[MAXN];
ll _pos_l[MAXN],_pos_r[MAXN];
struct query{
	ll l,r,id;
	bool operator < (const query &oth)const{
		return (l-1)/blen==(oth.l-1)/blen?(r<oth.r):(l-1)/blen<(oth.l-1)/blen;
	}
}Q[MAXN];
void add(ll X,ll &num){
	pos[a[X]].insert(X);
//	cout<<"/kel\n";
	num=max(num,(*(pos[a[X]].end()--))-(*pos[a[X]].begin()));
//	cout<<"/kk\n";
	return;
}
void del(ll X){
//	cout<<"now\n";
	pos[a[X]].erase(X);
//	cout<<"done\n";
	return;
}
vector<ll> que;
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	memcpy(tmp,a,sizeof(a));
//	for(int i=1;i<=n;i++)cout<<tmp[i]<<" ";
//	cout<<'\n'; 
	sort(tmp+1,tmp+1+n);
	ll qwq=unique(tmp+1,tmp+1+n)-tmp-1;
//	for(int i=1;i<=qwq;i++)cout<<tmp[i]<<" ";
//	cout<<'\n'; 
	for(int i=1;i<=n;i++)a[i]=lower_bound(tmp+1,tmp+1+qwq,a[i])-tmp;
//	for(int i=1;i<=n;i++)cout<<a[i]<<" ";
//	cout<<'\n';
	blen=sqrt(n);
	for(int i=1;i<=n;i+=blen){
		cnt++;
		b[cnt]=(block){i,min(i+blen-1,n)};
	}
//	for(int i=1;i<=cnt;i++)cout<<b[i].l<<" --- "<<b[i].r<<'\n';
	for(int i=1;i<=cnt;i++)for(int j=b[i].l;j<=b[i].r;j++)b_id[j]=i;
	cin>>q;
	for(int i=1;i<=q;i++){
		cin>>Q[i].l>>Q[i].r;
		Q[i].id=i;
	}
	sort(Q+1,Q+1+q);
	ll L=1,R=0,lst=0,_L=0;
	ll Ans=0,reg=0;
	for(int i=1;i<=q;i++){
		if(b_id[Q[i].l]==b_id[Q[i].r]){
			for(int j=Q[i].l;j<=Q[i].r;j++)_pos_l[a[j]]=1e9,_pos_r[a[j]]=0;
			for(ll j=Q[i].l;j<=Q[i].r;j++){
				_pos_l[a[j]]=min(_pos_l[a[j]],j);
				_pos_r[a[j]]=max(_pos_r[a[j]],j);
				ans[Q[i].id]=max(ans[Q[i].id],_pos_r[a[j]]-_pos_l[a[j]]);
			}
			for(int j=Q[i].l;j<=Q[i].r;j++)_pos_l[a[j]]=1e9,_pos_r[a[j]]=0;
			continue;
		}
		if(b_id[Q[i].l]!=lst){
			while(R>b[b_id[Q[i].l]].r)del(R),R--;
			while(L<b[b_id[Q[i].l]].r+1)del(L),L++;
			Ans=0;
			lst=b_id[Q[i].l];
		}
		while(R<Q[i].r)R++,add(R,Ans);
		reg=Ans;
		_L=L;
		while(_L>Q[i].l)_L--,add(_L,reg);
		ans[Q[i].id]=reg;
		while(_L<L)del(_L),_L++;
	}
	for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
	return 0;
}