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

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

int N, V[NMAX]; 

int binary_search0(int lo, int hi, int numar) 
{
	int mij = lo + (hi - lo)/2; 
	
	if((hi - lo) == 1) 
	{
		if(mij != N && V[mij+1] == numar) return mij+1; 
        if(V[mij] == numar) return mij; 
		else return -1; 
	}
	
	if(V[mij] <= numar) 
		return binary_search0(mij, hi, numar); 
	else return binary_search0(lo, mij, numar); 
}

int binary_search1(int lo, int hi, int numar) 
{
	int mij = lo + (hi - lo)/2; 
	
	if((hi - lo) == 1)
	{
		if(mij != N && V[mij+1] == numar) return mij+1; 
		if(V[mij] <= numar) return mij; 
		else return -1; 
	}
	
	if(V[mij] <= numar) 
		return binary_search1(mij, hi, numar); 
	else return binary_search1(lo, mij, numar); 
}

int binary_search2(int lo, int hi, int numar) 
{
	int mij = lo + (hi - lo)/2; 
	
	if((hi - lo) == 1) 
	{
		if(V[mij] >= numar ) return mij; 
		if(mij != N && V[mij+1] >= numar) return mij+1; 
		else return -1; 
	}
	
	if(V[mij] > numar) 
		return binary_search2(mij, hi, numar); 
	else return binary_search2(lo, mij, numar); 
}
	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 << binary_search0(1, N, nr) << '\n'; break;
		case 1 : out << binary_search1(1, N, nr) << '\n'; break;
		case 2 : out << binary_search2(1, N, nr) << '\n'; break; 
		}
	}
	}