#include<bits/stdc++.h>
using namespace std;
struct node
{
	int tot,l,r;
}tree[1<<24];
int cnt;
int root[1000001];
int n,a[1000001];
int clone(int x)
{
	tree[++cnt]=tree[x];
	return cnt;
}
void update(int x)
{
	tree[x].tot=tree[tree[x].l].tot+tree[tree[x].r].tot;
}
int change(int x,int k,int b,int L,int R)
{
	x=clone(x);
	if(L==R&&L==b)
	{
		tree[x].tot+=k;
		return x;
	}
	int m=(L+R)>>1;
	if(b<=m)
	{
		if(!tree[x].l) tree[x].l=++cnt;
		tree[x].l=change(tree[x].l,k,b,L,m);
	}
	else
	{
		if(!tree[x].r) tree[x].r=++cnt;
		tree[x].r=change(tree[x].r,k,b,m+1,R);
	}
	update(x);
	return x;
}
int query(int x,int l,int r,int L,int R)
{
	if(l>=L&&R<=r)
		return tree[x].tot;
	int m=(L+R)>>1,ans=0;
	if(l<=m)
	{
		if(!tree[x].l) tree[x].l=++cnt;
		ans+=query(tree[x].l,l,r,L,m);
	}
	if(m<r)
	{
		if(!tree[x].r) tree[x].r=++cnt;
		ans+=query(tree[x].r,l,r,m+1,R);
	}
	return ans; 
}
int main()
{
	int x,y;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		root[i]=change(root[i-1],a[i],a[i],1,1000000000);
	}
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>x>>y;
		int now=0;
		while(1)
		{
			int res=0;
			if(now>=1)
				res=query(root[y],1,now,1,1000000000)-query(root[x-1],1,now,1,1000000000);
			if(res>=now)
				now=res+1;
			else
				break;
		}
		cout<<now<<endl;
	}
}