#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(int x)
{
	int st,dr,m;
	st = 1;
	dr = n;
	while( st <= dr)
	{
		m = (st+dr)/2;
		if(a[m] == x )
			return m;
		if(a[m] > x)
			dr = m-1;
		else 
			st = m+1;
	}
	return -1;
}
int CautareBinaramicx(int x)
{
	//cea mai mare poz pe care se afla un nr <=x
	
	int st,dr,m, poz;
	st = 1;
	dr = n;
	while( st <= dr)
	{
		m = (st+dr)/2;
		if(a[m] == x )
		{
			while(a[m]==x && m <=n)
				++m;
			return m-1;
		}
		if(a[m] > x)
			dr = m-1;
		else 
		{
			poz = st;
			st = m+1;		
		}
	}
	return poz;
}
int CautareBinaramarex(int x)
{
	//cea mai mica poz pe care se afla un nr >=x
	
	int st,dr,m, poz;
	st = 1;
	dr = n;
	while( st <= dr)
	{
		m = (st+dr)/2;
		if(a[m] == x )
		{
			while(a[m]==x && m >=0)
				--m;
			return m+1;
		}
		if(a[m] > x)
		{
			poz = dr;
			dr = m-1;
		}
		else 
		{
		//	poz = st;
			st = m+1;		
		}
	}
	return poz;
}
void ReadData()
{
	int i,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;
}