#include <iostream>
using namespace std;
#include <fstream>

int highest_position_of___(int x, int* v, int N)
{
	int a = 1, b = N;//left and right positions
	bool found = false;
	if (x == v[N]) return N; //the highest possible position
	if (x == v[1]) found = true;//v[a] == x

	while (!found && v[a] < x && x < v[b])
	{
		int m = (a+b)/2;
		
		if (v[m] < x) a = m + 1;
		else if (x < v[m]) b = m - 1;
		else /* x == v[m] */ { found = true; a = m; }//ensures v[a] == x
	}

	if (found)//if found v[a] == x and x <= v[b]
	{
		//a good position was found, now seek for the highest position
		if (x == v[b]) return b;
		//otherwise
		while (!(v[a] == x && x < v[a+1]))//while the final condition is not met
		{
			int m = (a+b)/2;
			if (v[m] == x) a = m;
			else b = m;
		}

		return a;
	}

	return -1;//if not found
}

int highest_position_of_lower_or_equal_than(int x, int* v, int N)
{
	if (v[N] <= x) return N;
	//otherwise
	int a = 1, b = N;
	while (!(v[a] <= x && x < v[a+1]))//there exist such an index <<a>>
	{
		int m = (a+b)/2;
		if (v[m] <= x) a = m;
		else /* x < v[m] */ b = m;  
	}

	return a;
}

int lowest_position_of_higher_or_equal_than(int x, int* v, int N)
{
	if (x <= v[1]) return 1;	
	//otherwise
	int a = 1, b = N;	
	while (!(v[b-1] < x && x <= v[b]))//there exist such an index <<b>>
	{
		int m = (a+b)/2;
		if (v[m] < x) a = m;
		else /* x <= v[m] */ b = m;  
	}

	return b;
}

int highest_position_of(int x, int* v, int N)
{
	if ( x < v[1] || v[N] < x) return -1;
	//otherwise, v[1] <= x <= v[N]
	int a = highest_position_of_lower_or_equal_than(x, v, N);
	if (v[a] == x) return a;
	return -1;
}



//int cautare_binara()
int main()
{
	char* in_file = "cautbin.in";
	char* out_file = "cautbin.out";

	const int MAX_N = 100000;
	int v[MAX_N + 1];
	int N, M;

	ifstream ifs(in_file);
	ofstream ofs(out_file);

	ifs>>N;
	for (int i = 1; i <= N; i++) ifs>>v[i];
	ifs>>M;
	//processing; for each operation
	for (int m = 1; m <= M; m++)
	{
		int op;//operation type
		int x;
		ifs>>op>>x;

		switch (op)
		{
		case 0:
			ofs<<highest_position_of(x, v, N)<<"\n";
			break;
		case 1:
			ofs<<highest_position_of_lower_or_equal_than(x, v, N)<<"\n";
			break;
		case 2:
			ofs<<lowest_position_of_higher_or_equal_than(x, v, N)<<"\n";
			break;
		}
	}

	ifs.close();	
	ofs.close();

	return 0;
}