#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

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

int n, v[100001], x, numarCerinte, cerinta;

int cautareBinara0() {
	int rezultat = -1, stanga = 1, dreapta = n;
	while (stanga <= dreapta) {
		int mijloc = (stanga + dreapta) / 2;
		if (v[mijloc] == x) {
			rezultat = mijloc;
			stanga = mijloc + 1;
		}
		else
			if (v[mijloc] < x)
				stanga = mijloc + 1;
			else
				dreapta = mijloc - 1;

	}
	return rezultat;
}

int cautareBinara1() {
	int rezultat = -1, stanga = 1, dreapta = n;
	while (stanga <= dreapta) {
		int mijloc = (stanga + dreapta) / 2;
		if (v[mijloc] <= x) {
			rezultat = mijloc;
			stanga = mijloc + 1;
		}
		else
			if (v[mijloc] > x)
				dreapta = mijloc - 1;
			else
				stanga = mijloc + 1;
	}
	return rezultat;
}

int cautareBinara2() {
	int rezultat = -1, stanga = 1, dreapta = n;
	while (stanga <= dreapta) {
		int mijloc = (stanga + dreapta) / 2;
		if (v[mijloc] >= x) {
			rezultat = mijloc;
			dreapta = mijloc - 1;
		}
		else
			if (v[mijloc] < x)
				stanga = mijloc + 1;
			else
				dreapta = mijloc - 1;
	}
	return rezultat;
}

int main() {

	f >> n;
	for (int i = 1; i <= n; i++)
		f >> v[i];

	f >> numarCerinte;


	while (numarCerinte) {
		f >> cerinta >> x;
		if (cerinta == 0)
			g << cautareBinara0() << "\n";
		else
			if (cerinta == 1)
				g << cautareBinara1() << "\n";
			else
				if (cerinta == 2)
					g << cautareBinara2() << "\n";
		numarCerinte--;
	}

	return 0;
}