#include<fstream>
using namespace std;

ifstream in("cautbin.in");
ofstream out("cautbin.out");
const int Nmax = 100004;
int n,m;
int a[Nmax];

int CautareBinarax(long x)
{
	int st,dr,m;
	st = 1;
	dr = n;
	while( st <= dr)
	{
		m = (st+dr)/2;
		if(a[m] <= x )
			st = m+1;
		else
		if(a[m] > x)
			dr = m-1;
	}
	m = (st + dr )/2;
	if(a[m] > x)
		--m;
	if(a[m] == x)
		return m;
	return -1;
}
int CautareBinaramicx(long x)
{
	//cea mai mare poz pe care se afla un nr <=x
	
	int st,dr,m;
	st = 1;
	dr = n;
	while( st < dr)
	{
		m = (st+dr)/2;
		if(a[m] > x)
			dr = m;
		else 
			st = m+1;		
	}
	m=(st+dr)/2;
	if(a[m] >x)
		--m;
	return m;
}
int CautareBinaramarex(long x)
{
	//cea mai mica poz pe care se afla un nr >=x
	
	int st,dr,m;
	st = 1;
	dr = n;
	while( st < dr)
	{
		m = (st+dr)/2;
		if(a[m] >= x)
			dr = m;
		else 
			st = m+1;		
	}
	m = (st + dr) / 2;
	if (a[m] < x)
		++ m;
	return m;
}
void ReadData()
{
	int i;
	long x,y;
	in>>n;
	for( i=1; i<=n; i++)
	{
		in>>a[i];
	}
	in>>m;
	for( i=1;i<=m;i++)
	{
		in>>x>>y;
		if(x == 0) 
			out<<CautareBinarax(y)<<"\n";
		else
		if(x == 1)
			out<<CautareBinaramicx(y)<<"\n";
		else
		if(x == 2)
			out<<CautareBinaramarex(y)<<"\n";
	}
}
int main()
{
	ReadData();
	return 0;
}