#include<fstream> 
#define NMAX 100001
using namespace std; 

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

int N, V[NMAX]; 

int bs0(int numar) 
{
	int lo, hi, mij, last = 0; 
	
	for(lo = 1, hi = N; lo <= hi;) 
	{
		mij = lo + (hi - lo)/2; 
		if(V[mij] <= numar) last = mij, lo = mij + 1; 
		else 
			hi = mij - 1; 
	}
	if(V[last] == numar) return last;
	else return -1; 
}

int bs1(int numar) 
{
	int lo, hi, mij, last = 0; 
	
	for(lo = 1, hi = N; lo <= hi;) 
	{
		mij = lo + (hi - lo)/2; 
		if( V[mij] <= numar) last = mij, lo = mij + 1; 
		else 
			hi = mij - 1; 
	}
	return last; 
}

int bs2(int numar) 
{
	int lo, hi, mij, last = 0; 
	
	for(lo = 1, hi = N; lo <= hi;) 
	{
		mij = lo + (hi - lo)/2; 
		if(V[mij] >= numar) last = mij, hi = mij - 1; 
		else 
			lo = mij + 1; 
	}
	return last; 
}
	
	int main()  
{
	int M, i, cod, nr; 
	
	in >> N; 
	for(i = 1; i <= N; i++) 
		in >> V[i]; 
	in >> M; 
	for(i = 1; i <= M; i++)
	{
		in >> cod >> nr; 
		switch(cod)
		{
		case 0 : out << bs0(nr) << '\n'; break;
		case 1 : out << bs1(nr) << '\n'; break;
		case 2 : out << bs2(nr) << '\n'; break; 
		}
	}
	}