#include <fstream>
#include <vector>

using namespace std;


//CAUTARE BINARA (ARH EDUCATIONALA)

int vec[100001];
int n;

int highXValue(int val);
int XValue(int val);
int smallXValue(int val);

int main()
{
	//declararea fisierelor de intrare/iesire
	ifstream IN("cautbin.in");
	ofstream OUT("cautbin.out");

	//vector de functii pentru inlaturarea conditionalelor din for
	std::vector<int(*) (int val)> functions;
	functions.push_back(XValue);
	functions.push_back(highXValue);
	functions.push_back(smallXValue);

	//se citeste nr de numere din vector
	IN >> n;

	//se citesc numere din lista
	for (int i = 0 ; i < n; i++)
	{
		IN >> vec[i];
	}

	//se citeste numarul de intrebari
	int m; IN >> m;
	unsigned int type, val;

	int ret;

	//se iau intrebarile in ordine 
	for (int i = 0; i < m; i++)
	{
		//se citesc componentele intrebarii
		IN >> type; IN >> val;
		ret = functions[type](val);


		OUT << ret + 1 << "\n";
	}

	return 0;
}

int XValue(int val)
{
	int lo = 0, high = n - 1, pivot;

	while(lo <= high)
	{
		pivot = lo + (high - lo)/2;

		if (vec[pivot] <= val)
			lo = pivot + 1;

		else if (vec[pivot] > val)
			high = pivot - 1;
	}

	if (vec[pivot] == val)
		return pivot;
	else 
		return -2;
}

int highXValue(int val)
{
	int lo = 0, high = n - 1, pivot;

	while (lo <= high)
	{
		pivot = lo + (high - lo) / 2;

		if (vec[pivot] <= val)
			lo = pivot + 1;
		
		else if (vec[pivot] > val)
			high = pivot - 1;
	}

	return high;
}

int smallXValue(int val)
{
	int lo = 0, high = n - 1, pivot;

	while ( lo <= high)
	{
		pivot = lo + (high - lo) / 2;

		if (vec[pivot] < val)
			lo = pivot + 1;

		else
			high = pivot - 1;
	}

	return lo;
}