#include<stdio.h>
int main()
{
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	int n,ma,i,t,st,dr,y,p,j,m;
	scanf("%d",&n);
	int v[n+5];
	for(i=1;i<=n;i++)
		scanf("%d",&v[i]);
	scanf("%d",&ma);
	for(i=1;i<=ma;i++)
	{
		scanf("%d%d",&t,&y);
		//pt t=0
		if(t==0)
		{
	dr=n;
	st=1;
	while(st<=dr)
	{
			m=(st+dr)/2;
	if(v[m]<=y)
		st=m+1;
	else
		dr=m-1;
	}
	if(v[m]>y)
		m--;
	printf("%d\n",m);
		}
		//pt t=1
		else
			if(t==1)
		{
					p=-1;
	dr=n;
	st=1;
	while(dr>st)
	{
		m=(st+dr)/2;
	if(v[m]<=y)
		st=m+1;
		else
			dr=m;
	}
	p=(st+dr)/2;
	if(v[(st+dr)/2]>y)
		p--;
	printf("%d\n",p);
		}
	//pt t=2
	else
	{
		dr=n;
		st=1;
		while(dr>st)
		{
			m=(st+dr)/2;
			if(v[m]<y)
			st=m+1;
			else
				dr=m;
		}
		m=(st+dr)/2;
		if(v[m]<y)
			m--;
		printf("%d\n",m);
	}
	}
	return 0;
}