#include<bits/stdc++.h>
//#include <bits/extc++.h>

//using namespace __gnu_pbds;
//using namespace __gnu_cxx;
using namespace std;

const int N=200005,Block=600;

int n,m;
int arr[N];

int gblock(int num) {return (num-1)/Block+1;}

struct Node {int l,r,id;};
vector<Node> qst[Block];

int block[N];

int b[N];
unordered_map<int,int> M;
void calc() {
	for(int i=1;i<=n;++i) b[i]=arr[i];
	sort(b+1,b+1+n);
	int cnt=0;
	for(int i=1;i<=n;++i) if(!M[b[i]]) M[b[i]]=++cnt;
	for(int i=1;i<=n;++i) arr[i]=M[arr[i]];
}

int dis;

void upd(int num);

struct node {
	int L[N],R[N],dis;
	node() {memset(L,63,sizeof(L));}
	void ins(int num,int p) {
		L[num]=min(L[num],p);
		R[num]=max(R[num],p);
		upd(num);dis=max(dis,R[num]-L[num]);
	}
	void del(int num) {L[num]=1e9,R[num]=0;}
}L,R;

void upd(int num) {dis=max(dis,R.R[num]-L.L[num]);}

int ans[N];
int main() {
	cin >> n;
	for(int i=1;i<=n;++i) cin >> arr[i];
	
	calc();
	for(int i=1;i<=n;++i) block[i]=gblock(i);
	
	cin >> m;
	int l,r;
	for(int i=1;i<=m;++i) {
		cin >> l >> r;
		qst[block[l]].push_back({l,r,i});
	}
	for(int i=1;(i-1)*Block+1<=n;++i) 
		sort(qst[i].begin(),qst[i].end(),[&](Node a,Node b) -> bool {return a.r<b.r;});
	
	for(int i=1;(i-1)*Block+1<=n;++i) {
		memset(R.R,0,sizeof(R.R));
		memset(R.L,63,sizeof(R.L));
		R.dis=0;
		
		int p=i*Block+1;
		
		for(auto& [l,r,id]:qst[i]) {
			dis=0,L.dis=0;
			for(int j=min(r,i*Block);j>=l;--j) L.ins(arr[j],j);
			
			while(p<=r) R.ins(arr[p],p++);
			
			for(int j=min(r,i*Block);j>=l;--j) L.del(arr[j]);
			ans[id]=max({dis,L.dis,R.dis});
		}
	}
	
	for(int i=1;i<=m;++i) cout << ans[i] << '\n';
	
	return 0;
}