#include <fstream>
using namespace std;
#define dim 100000

int v[dim], n;


ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

void citire()
{
	
	fin>>n;
	for(int i=1;i<=n;++i)
		fin>>v[i];
}

int caz1(int ls,int ld,int nr)
{
	int mijloc, gasit=0;
	
	while(ls<=ld && !gasit)
	{
		mijloc=(ls+ld)>>1;
		if(v[mijloc]==nr)
			gasit=1;
		else
			if (v[mijloc]<nr)
			ls=mijloc+1;
		else
			ld=mijloc-1;
	}
	
	if (!gasit)
			return -1;
	
	if(v[mijloc]==nr)
		++mijloc;
	
	return mijloc;
	
}

int caz2(int ls,int ld,int nr)
{
	int mijloc;

	while(ls<ld)
	{
		mijloc=(ls+ld)>>1;
		if(v[mijloc]<=nr)
			ls=mijloc+1;
		else
			ld=mijloc;
	}
	mijloc=(ls+ld)>>1;
	if(v[mijloc]>nr)
		--mijloc;
	
	return mijloc;
}

int caz3(int ls,int ld,int nr)
{
	int mijloc;
	int aux=nr;
	while(ls<ld)
	{
		mijloc=(ls+ld)>>1;
		if(v[mijloc]<nr)
			ls=mijloc+1;
		else
			ld=mijloc;
	}
	mijloc=(ls+ld)>>1;
	if(v[mijloc]>nr)
		++mijloc;
	
	return mijloc;
}

int main()
{
	int m, i, a, b, rez;
	citire();
	fin>>m;
	for(i=1;i<=m;++i)
	{
		fin>>a >>b;
		if(a==0)
		{
			rez=caz1(1,n,b);
			fout<<rez <<'\n';
		}
		if(a==1)
		{
			rez=caz2(1,n,b);
			fout<<rez <<'\n';
		}
		if(a==2)
		{
			rez=caz3(1,n,b);
			fout<<rez <<'\n';
		}
	}
	return 0;
}