#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;

inline int read(){
	int ret=0;
	char ch=' ',c=getchar();
	while(!('0'<=c&&c<='9')) ch=c,c=getchar();
	while('0'<=c&&c<='9') ret=(ret<<1)+(ret<<3)+(c^48),c=getchar();
	return ch=='-'?-ret:ret;
}

int n,m;
const int N=2e5+10,M=2e5+10,V=2e5+10;
int a[N],b[N];
inline int getval(int x){
	int l=1,r=n,mid;
	while(l<r){
		mid=(l+r)>>1;
		if(b[mid]>=x) r=mid;
		else l=mid+1;
	}
	return l;
}

int id[N],len;
inline void getid(){
	len=sqrt(n);
	for(int i=1;i<=n;i++) id[i]=(i-1)/len+1;
}

struct query{
	int num;
	int l,r;
} q[M];
int res[M];
int mn[V],mx[V];
int tmn[V],tmx[V];

bool cmp(query &A,query &B){
	if(id[A.l]!=id[B.l]) return id[A.l]<id[B.l];
	else return A.r<B.r;
}

int main(){
	memset(mn,0x7f,sizeof(mn));
	n=read();
	for(int i=1;i<=n;i++) b[i]=a[i]=read();
	sort(b+1,b+1+n);
	for(int i=1;i<=n;i++) a[i]=getval(a[i]);
	m=read();
	getid();
	for(int i=1;i<=m;i++){
		q[i].num=i;
		q[i].l=read();
		q[i].r=read();
	}
	sort(q+1,q+1+m,cmp);
	int x=1,y=1;
	int ans=0;
	while(y<=m){
		ans=0;
		while(y<=m&&id[q[x].l]==id[q[y].l]) y++;
		y--;
		int R=id[q[x].l]*len;
		while(x<=y&&id[q[x].l]==id[q[x].r]){
			int l=q[x].l;
			int r=q[x].r;
			for(int i=r;i>=l;i--){
				mn[a[i]]=min(mn[a[i]],i);
				mx[a[i]]=max(mx[a[i]],i);
				ans=max(ans,mx[a[i]]-mn[a[i]]);
			}
			res[q[x].num]=ans;
			for(int i=l;i<=r;i++){
				mn[a[i]]=0x7f7f7f7f;
				mx[a[i]]=0;
			}
			ans=0;
			x++;
		}
		int s=R+1,t=R;
		while(x<=y){
			int l=q[x].l;
			int r=q[x].r;
			while(r>t){
				t++;
				mn[a[t]]=min(mn[a[t]],t);
				mx[a[t]]=max(mx[a[t]],t);
				ans=max(ans,mx[a[t]]-mn[a[t]]);
			}
			int backup=ans;
			while(l<s){
				s--;
				tmn[a[s]]=mn[a[s]];
				tmx[a[s]]=mx[a[s]];
				mn[a[s]]=min(mn[a[s]],s);
				mx[a[s]]=max(mx[a[s]],s);
				ans=max(ans,mx[a[s]]-mn[a[s]]);
			}
			res[q[x].num]=ans;
			ans=backup;
			while(s<=R){
				mn[a[s]]=tmn[a[s]];
				mx[a[s]]=tmx[a[s]];
				s++;
			}
			x++;
		}
		memset(mn,0x7f,sizeof(mn));
		memset(mx,0,sizeof(mx));
		y=x;
	}
	for(int i=1;i<=m;i++) printf("%d\n",res[i]);
	return 0;
}