#include<stdio.h>
int n,m1,v[100000],x,intr;
void citire()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		scanf("%d",&v[i]);
	scanf("%d",&m1);
}
int op0()
{
	int dr=n,st=1,m;
	m=(st+dr)/2;
	while(x!=v[m])
	{
		if(x>v[m])
		{
			st=m;
			m=(st+dr)/2;
		}
		else if(x<v[m])
		{
			dr=m;
			m=(st+dr)/2;
		}
	}
	return m;
}
int op1()
{
	int dr=n,st=1,m;
	m=(st+dr)/2;
	if(x==v[m])
		return m-1;
	while(x>v[m])
	{
		st=m;
		m=(st+dr)/2;
	}
	while(x<v[m])
	{
		dr=m;
		m=(st+dr)/2;
	}
	return m;
}
int op2()
{
	int dr=n,st=1,m;
	m=(st+dr)/2;
	if(x==v[m])
		return m+1;
	while(x<v[m])
	{
		dr=m;
		m=(st+dr)/2;
	}
	while(x>v[m])
	{
		st=m;
		m=(st+dr)/2;
	}
	return m;
}
int main()
{
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	citire();
	for(int i=1;i<=m1;++i)
	{
		scanf("%d%d",&intr,&x);
		if(intr==0)
			printf("%d\n",op0());
		if(intr==1)
			printf("%d\n",op1());
		if(intr==2)
			printf("%d\n",op2());
	}
	return 0;
}