rt.

#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 114514<<1;

int n,m,l,r,blo,cnt,lal,tmp,tmm,pre = -1,a[N],pr[N],st[N],ed[N],ped[N],pos[N],ans[N];

struct query{int l,r,id;}b[N];
bool query_cmp(query a,query b){return (pos[a.l] == pos[b.l] ? a.r < b.r : pos[a.l] < pos[b.l]);}
struct discretization{int x,id;}dis[N];
bool discretization_cmp(discretization a,discretization b){return a.x < b.x;}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	cin >> n;blo = sqrt(n);
	for(int i = 1;i <= n;++i){
		cin >> dis[i].x;
		dis[i].id = i;
		pos[i] = (i-1)/blo + 1;
	}
	for(int i = 1;i <= pos[n];++i) pr[i] = ((pos[n] == i) ? n : i*blo);
	cin >> m;
	for(int i = 1;i <= m;++i){
		b[i].id = i;
		cin >> b[i].l >> b[i].r;
	}
	sort(b+1,b+m+1,query_cmp);
	sort(dis+1,dis+n+1,discretization_cmp);
	for(int i = 1;i <= n;++i){
		if(dis[i].x != pre) ++cnt;
		a[dis[i].id] = cnt;
		pre = dis[i].x;
	}
	for(int i = 1;i <= m;++i){
		if(pos[b[i].l] == pos[b[i].r]){
			tmp = 0;
			for(int j = b[i].l;j <= b[i].r;++j) st[a[j]] = 0;
			for(int j = b[i].l;j <= b[i].r;++j){
				if(!st[a[j]]) st[a[j]] = j;
				tmp = max(tmp,j-st[a[j]]);
			}
			for(int j = b[i].l;j <= b[i].r;++j) st[a[j]] = 0;
			ans[b[i].id] = tmp;
			continue;
		}
		int xy = pos[b[i].l];
		if(lal != xy){
			tmp = 0;
			for(int j = l;j <= r;++j) st[a[j]] = ed[a[j]] = 0;
			l = pr[xy];
			r = l-1;
			lal = xy;
		}
		while(r < b[i].r){
			if(!st[a[++r]]) st[a[r]] = r;
			ed[a[r]] = r;
			tmp = max(tmp,r-st[a[r]]);
		}
		int p = l;tmm = 0;
		while(b[i].l < p--){
			if(!ped[a[p]]) ped[a[p]] = p;
			tmm = max(tmm,max(ed[a[p]],ped[a[p]]-p));
		}
		while(p < l) ped[a[p++]] = 0;
		ans[b[i].id] = max(tmp,tmm);
	}
	for(int i = 1;i <= m;++i) cout << ans[i] << '\n';
	return 0;
}