#include <fstream>
#include <vector>

using namespace std;

//the vector + the size of the vector
int vec[100001], n;

// cea mai mare pozitie pe care se afla un element cu valoarea x sau -1 daca aceasta valoare nu se gaseste in sir
int XValue(int val);

// cea mai mare pozitie pe care se afla un element cu valoarea mai mica sau egala cu x in sir.
// Se garanteaza ca cel mai mic numar al sirului este mai mic sau egal decat x 
int HighestX(int val);

//  cea mai mica pozitie pe care se afla un element cu valoarea mai mare sau egala cu x in sir.
//  Se garanteaza ca cel mai mare numar din sir este mai mare sau egal decat x
int SmallestX(int val);

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

	//vector ce contine pointeri catre functii
	vector<int(*)(int)> functions;
	functions.push_back(XValue);
	functions.push_back(HighestX);
	functions.push_back(SmallestX);

	//citirea numerelor in vector
	IN >> n;
	for (int i = 0; i < n; i++)
		IN >> vec[i];

	//citirea numarului de intrebari
	int m; IN >> m;

	//citeste toate intrebarile si raspunde-le
	for (int i = 0 ; i < m ; i++)
	{
		//citeste tipul intrebarii si valoarea asociata
		int type, val; IN >> type; IN >> val;

		//afiseaza raspunsul
		OUT << functions[type](val) + 1 << "\n";
	}

	//programul s-a incheiat cu bine
	return 0;
}

int XValue (int val)
{
	//se fixeaza marginea inferioara (lo)
	//cea superioara (hi)
	//si pivotul
	int lo = 0, hi = n - 1, pivot;


	//atat timp cat marginile nu au trecut una de cealalta
	while (lo <= hi)
	{
		// se calculeaza pivotul
		// "De asemenea pot aparea erori in cazul in care capetele intervalului pot lua si valori negative.
		// De aceea se recomanda scrierea instructiunii mid = lo + (hi-lo)/2 in loc de mid = (st+dr)/2."
		pivot = lo + (hi - lo) / 2;


		//daca valoarea actuala indicata de pivot este mai mica sau egala decat valoarea
		//cautata atunci urmatorul element dupa pivot devine marginea inferioara
		// deoarece vom cauta cea mai mare pozitie pe care se afla numarul val
		if (vec[pivot] <= val)
			lo = pivot + 1;

		//daca valoarea indicata de pivot este mai mare atunci 
		//marginea inferioara devine elementul dinaintea pivotului
		else
			hi = pivot - 1;
	}

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

int HighestX(int val)
{
	int lo = 0, hi = n - 1, pivot;

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

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

	return hi;
}

int SmallestX(int val)
{
	int lo = 0, hi = n - 1, pivot;

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

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

	return lo;
}