/*
int i,pas=(1<<k);
for(i=0;pas!=0;pas=pas/2) || pas>>=1
	if(i+pas are prop)
		i+=pas;
i este ultimul cu prop

int i,pas=(1<<16);
for(i=0;pas!=0;pas>>=1)
	if(i+pas<=x && v[i+pas] <=x
		i+=pasl
if(v[i]!=x)
	return -1;
return i;
*/

#include <stdio.h>

int v[100000];

int bs0(int x,int n)
{
	int i,pas=1<<16;
	for(i=0;pas!=0;pas>>=1)
		if(i+pas<=n && v[i+pas] <=x)
			i+=pas;
	if(v[i]!=x)
		return -1;
	return i;
}

int bs1(int x,int n)
{
	int i,pas=1<<16;
	for(i=0;pas!=0;pas>>=1)
		if(i+pas<=n && v[i+pas] <=x)
			i+=pas;
	return i;
}
int bs2(int x,int n)
{
	int i,pas=1<<16;
	for(i=0;pas!=0;pas>>=1)
		if(i+pas<=n && v[i+pas] < x)
			i+=pas;
	if(i<=n-1)
		return i+1;
	return i;
}
int main()
{
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	int n,m,i,p,tip,x;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&v[i]);
	scanf("%d",&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&tip,&x);
		if(tip==0)
			p=bs0(x,n);
		else
		if(tip==1)
			p=bs1(x,n);
		else
		if(tip=2)
			p=bs2(x,n);
		printf("%d\n",p);
	}
	
	return 0;
}