#include <fstream>

using namespace std;

#define N 100000

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int v[N];

int binSearch(int value, int numElem) {
	int i, step;

	for (step = 1; step < numElem; step <<= 1);
	for (i = 0; step; step >>= 1) {
		if (i + step < numElem && v[i + step] <= value)
			i += step;
	}

	return i;
}

int main() {
	int numElem, numQuery, type, value;
	fin >> numElem;
	for (int i = 0; i < numElem; i++)
		fin >> v[i];

	fin >> numQuery;
	while (numQuery) {
		fin >> type >> value;
		if (type == 2) {
			int pos = binSearch(value - 1, numElem);
			fout << pos + 1 << "\n";
		} else {
			int pos = binSearch(value, numElem);
			if (type == 1) {
				fout << pos << "\n";
			} else {
				if (v[pos] == value) {
					fout << pos << "\n";
				} else {
					fout << -1 << "\n";
				}
			}
		}
		/*
		switch (type) {
			case 0: {
				int pos = binSearch(value, numElem);
				if (v[pos] == value)
					fout << pos + 1 << "\n";
				else
					fout << -1 << "\n";
				break;
			}
			case 1: {
				int pos = binSearch(value, numElem);
				fout << pos + 1 << "\n";
				break;
			}
			case 2: {
				int pos = binSearch(value - 1, numElem);
				fout << pos + 2 << "\n";
				break;
			}
		}
		*/
		numQuery--;
	}

	return 0;
}