#include <fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int n,m,v[100001];
int bs0(int val)
{
	int l=1,r=n,m,sol=-1;
	while(l<=r)
	{
		m=(l+r)/2;
		if(v[m]==val)
			sol=m;
		if(v[m]>val)
			r=m-1;
		else
			l=m+1;
	}
	return sol;
}
int bs1(int val)
{
	int l=1,r=n,m,sol;
	while(l<=r)
	{
		m=(l+r)/2;
		if(v[m]<=val)
		{
			sol=m;
			l=m+1;
		}
		else
			r=m-1;
	}
	return sol;
}
int bs2(int val)
{
	int l=1,r=n,m,sol;
	while(l<=r)
	{
		m=(l+r)/2;
		if(v[m]>=val)
		{
			sol=m;
			r=m-1;
		}
		else
			l=m+1;
	}
	return sol;
}
int main()
{
	fin>>n;
	for(int i=1;i<=n;i++)
		fin>>v[i];
	int cmd,x;
	fin>>m;
	while(m--)
	{
		fin>>cmd>>x;
		switch(cmd)
		{
			case 0:
			fout<<bs0(x)<<'\n';
			break;
			case 1:
			fout<<bs1(x)<<'\n';
			break;
			default:
			fout<<bs2(x)<<'\n';
		}
	}
	fin.close();
	fout.close();
	return 0;
}