#include <fstream>
#include <vector>
#include <ctime>
#include <iostream>

using namespace std;


//CAUTARE BINARA (ARH EDUCATIONALA)

vector<int> vec;

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, vector<int>& vec)> functions;
	functions.push_back(XValue);
	functions.push_back(smallXValue);
	functions.push_back(highXValue);*/

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

	//se aloca dinamic memorie pt n numere in vector

	int x;

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

	//se citeste numarul de intrebari
	int m; IN >> m;
	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;
		if (type == 0)
			ret = XValue(val);
		else if (type == 1)
			ret = highXValue(val);
		else if (type == 2)
			ret = smallXValue(val);

		ret++;

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


	return 0;
}

int XValue (int val)
{
	int low = 0 , high = vec.size() - 1, pivot = (low + high) / 2;

	while (vec[pivot] != val && low != high)
	{
		pivot = (low + high) / 2;
		if (vec[pivot] > val)
		{
			high = pivot;
		}

		else if (vec[pivot] < val)
		{
			low = pivot;
		}
	}

	if (vec[pivot] == val)
	{
		while((pivot + 1) <= vec.size() - 1 && vec[pivot + 1] == vec[pivot])
			pivot++;

		return pivot;
	}
	else return -1;
}


int highXValue(int val)
{
	int low = 0, high = vec.size() - 1, pivot = (low + high) / 2;

	while (vec[pivot] != val && low != high)
	{
		pivot = (low + high) / 2;
		if (vec[pivot] > val)
		{
			high = pivot;
		}

		else if (vec[pivot] < val)
		{
			low = pivot;
		}
	}

	if (vec[pivot] == val)
	{
		while((pivot + 1) <= vec.size() - 1 && vec[pivot + 1] == vec[pivot])
			pivot++;
	}

	else if (vec[pivot] > val)
	{
		while (vec[pivot] > val)
			pivot--;

		pivot++;
	}

	else if (vec[pivot] < val)
	{
		while (vec[pivot] < val)
			pivot++;

		pivot--;
	}

	return pivot;
}

int smallXValue(int val)
{
	int low = 0, high = vec.size() - 1, pivot = (low + high) / 2;

	while (vec[pivot] != val && low != high)
	{
		pivot = (low + high) / 2;
		if (vec[pivot] > val)
		{
			high = pivot;
		}

		else if (vec[pivot] < val)
		{
			low = pivot;
		}
	}

	if (vec[pivot] == val)
	{
		while((pivot - 1) >= 0 && vec[pivot - 1] == vec[pivot])
			pivot--;
	}

	else if (vec[pivot] > val)
	{
		while (vec[pivot] > val)
			pivot--;

		pivot++;
	}

	else if (vec[pivot] < val)
	{
		while (vec[pivot] < val)
			pivot++;

		pivot--;
	}

	return pivot;

}