#include <bits/stdc++.h>
using namespace std;
const int N=1e7;
int n,m;
int L[N],R[N],sum[N],rt[N],tot;
int change(int p,int l,int r,int pos,int v)
{
	int rt=++tot;
	L[rt]=L[p];
	R[rt]=R[p];
	sum[rt]=sum[p]+v;
	if(l==r)
	return rt;
	int mid=(l+r)>>1;
	if(pos<=mid)
	L[rt]=change(L[rt],l,mid,pos,v);
	else
	R[rt]=change(R[rt],mid+1,r,pos,v);
	return rt;
}
int query(int u,int v,int l,int r,int s,int t)
{
	if(s<=l&&t>=r)
	return sum[v]-sum[u];
	int mid=(l+r)>>1;
	int ans=0;
	if(s<=mid)
	ans+=query(L[u],L[v],l,mid,s,t);
	if(t>mid)
	ans+=query(R[u],R[v],mid+1,r,s,t);
	return ans;
}
int a[N];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		rt[i]=change(rt[i-1],1,N,a[i],a[i]);
	}
	cin>>m;
	while(m--)
	{
		int l,r;
		cin>>l>>r;
		int ans=1;
		for(;;)
		{
			int res=query(rt[l-1],rt[r],1,N,1,ans);
			if(res>=ans)
			ans=res+1;
			else
			break;
		}
		cout<<ans<<endl;
	}
}