// Problem: AT1219 歴史の研究
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/AT1219
// Memory Limit: 500 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <stdio.h>
#include <string.h> 
#include <algorithm>
#include <queue>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;
inline int read()
{
	int num=0,f=1;char c=getchar();
	while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
	while(c>47&&c<58)num=num*10+(c^48),c=getchar();
	return num*f;
}
inline int re1d()
{
	char c=getchar();
	while(c<48||c>49)c=getchar();
	return c&1;
}
inline int min(int a,int b){return a>b?b:a;}
inline int max(int a,int b){return a<b?b:a;}
struct Queries{
	int l,r,lb,rb,i;
	bool operator<(const Queries &b)const
	{
		return lb==b.lb?r<b.r:lb<b.lb;
	}
}q[200005];
int a[200005],c[200005];
gp_hash_table<int,int> L,R,tL,tR;
//int L[200005],R[200005],tL[200005],tR[200005];
const int B=450;
int ans=0;
//#define add(x) if(b[a[x]])ans=max(ans,a[x])
inline void add(int x)
{
	if(L[a[x]]==0)
	{
		L[a[x]]=R[a[x]]=x;
		return;
	}
	ans=max(ans,max(x-L[a[x]],R[a[x]]-x));
	L[a[x]]=min(L[a[x]],x);
	R[a[x]]=max(R[a[x]],x);
}
signed main()
{
	int n=read();//,m=read();
	for(int i=1;i<=n;i++)a[i]=read();
	int m=read();
	for(int i=1;i<=m;i++)q[i].i=i,q[i].l=read(),q[i].r=read(),q[i].lb=q[i].l/B,q[i].rb=q[i].r/B;
	std::sort(q+1,q+1+m);q[0].lb=-1;
	int cl=1,cr=0;
	for(int i=1;i<=m;i++)
	{
		int l=q[i].l,r=q[i].r,lb=q[i].lb,rb=q[i].rb;
		if(lb==rb)
		{
			L.clear();
			R.clear();
			cl=l,cr=l-1,ans=0;
			while(cr<r)++cr,add(cr);
			c[q[i].i]=ans;
//			for(int i=l;i<=cr;i++)b[a[i]]--;
			L.clear();R.clear();
			cl=(lb+1)*B,cr=cl-1,ans=0;
			continue;
		}
		int t;
		if(q[i].lb!=q[i-1].lb)ans=0,cl=(lb+1)*B,cr=cl-1,L.clear(),R.clear();
		while(cr<r)++cr,add(cr);
		t=ans;
		int Q=cl;
		//		tL=L,tR=R;
		for(int i=l;i<cl;i++)tL[a[i]]=L[a[i]],tR[a[i]]=R[a[i]];
		while(Q>l)--Q,add(Q);
		for(int i=Q;i<cl;i++)L[a[i]]=tL[a[i]],R[a[i]]=tR[a[i]];
		//L=tL,R=tR;
		c[q[i].i]=ans;
		ans=t;
	}
	for(int i=1;i<=m;i++)printf("%d\n",c[i]);
}