#include<bits/stdc++.h>

#define lson ls[x]

#define mid ((l+r)>>1)

#define rson rs[x]

#define maxn 300003

#define inf 1000000001

#define setIO(s) freopen(s".in","r",stdin)

using namespace std;

int cnt;

int ls[maxn*20], rs[maxn*20], sumv[maxn*20], root[maxn];

void build(int &x,int l,int r)

{

	x=++cnt;

	if(l==r)return;

	if(mid>=l) build(lson, l,mid);

	if(r>mid) build(rson,mid+1,r);

}

int update(int x,int l,int r,int k,int delta)

{

	int oo=++cnt;

	ls[oo]=ls[x], rs[oo]=rs[x], sumv[oo]=sumv[x]+delta;

	if(l==r) return oo;

	if(k<=mid) ls[oo]=update(lson,l,mid,k,delta);

	else rs[oo]=update(rson,mid+1,r,k,delta);

	return oo;

}

int query(int u,int v,int l,int r,int L,int R)

{

	if(l>=L&&r<=R) return sumv[v]-sumv[u];

	int tmp=0;

	if(L<=mid) tmp+=query(ls[u],ls[v],l,mid,L,R);

	if(R>mid) tmp+=query(rs[u],rs[v],mid+1,r,L,R);

	return tmp;

}

int main()

{

	// setIO("input");

	int n,q,i,a,l,r;

	scanf("%d",&n);

	for(i=1;i<=n;++i)

	{

		scanf("%d",&a);

		root[i]=update(root[i-1],1,inf,a,a);

	}

	scanf("%d",&q);

	while(q--)

	{

		scanf("%d%d",&l,&r);

		int mx=0,pos=0,sum;

		while(1)

		{

			sum=query(root[l-1],root[r],1,inf,mx+1,pos+1);

			if(sum<=0) break;

			mx=pos+1, pos+=sum;

		}

		printf("%d\n",pos+1);

	}

	return 0;

}