#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
using namespace std;
const int N=2000000;
int n,Q,d,a[N+5],fl[N+5],fr[N+5],qans[N+5],bl,ans,bans,b[N+5];
//map<int,int> fl,fr;
struct node{
	int l,r,id;
}q[N+5]; 
bool operator <(const node &a,const node &b){
	return a.l/bl^b.l/bl?a.l<b.l:a.r<b.r;
}
void add(int pos){
	if (fl[b[pos]]==0) fl[b[pos]]=pos;
	if (fr[b[pos]]==0) fr[b[pos]]=pos;
	fr[b[pos]]=max(pos,fr[b[pos]]);
	fl[b[pos]]=min(pos,fl[b[pos]]);
	ans=max(ans,fr[b[pos]]-fl[b[pos]]);
	//NOT ans=fr[a[pos]]-fl[a[pos]]
}
int main(){
	ios::sync_with_stdio(0);
	cin>>n;
	bl=sqrt(n);
	for (int i=1;i<=n;i++){
		cin>>a[i];
		b[i]=a[i];
	}
	sort(a+1,a+n+1);
	d=unique(a+1,a+n+1)-a-1;
	for (int i=1;i<=n;i++) b[i]=lower_bound(a+1,a+d+1,b[i])-a-1;
	cin>>Q;
	for (int i=1;i<=Q;i++){
		cin>>q[i].l>>q[i].r;
		q[i].id=i;
		if (q[i].l/bl==q[i].r/bl){
			for (int j=q[i].l;j<=q[i].r;j++) add(j);
			qans[i]=ans,ans=0;
			for (int j=q[i].r;j>=q[i].l;j--) fr[b[j]]=fl[b[j]]=0;
			q[i].l=n+1;
		}
	}
	sort(q+1,q+Q+1);
	int L=bl,R=bl-1;
	for (int i=1,bi=0;q[i].l<=n&&i<=Q;i++){
		if (bi^q[i].l/bl){
			bi=q[i].l/bl;
			bans=ans=0,L=bi*bl+bl,R=L-1;
			while (L<bi*bl+bl) fl[b[L++]]=0;
			while (R>L-1) fr[b[R--]]=0;
		}
		while (R<q[i].r) add(++R);
		bans=ans;
		while (L>q[i].l) add(--L);
		qans[q[i].id]=ans;
		while (L<bi*bl+bl) fl[b[L++]]=0;
		ans=bans;
	}
	for (int i=1;i<=Q;i++)
		cout<<qans[i]<<'\n';	
}