#include <fstream>

using namespace std;

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

int N, T, V[100003];

int bsearch0(int V[], int N, int val) {
	int log;
	for (log = 1; log << 1 <= N; log <<= 1);
	int ans;
	for (ans = 0; log; log >>= 1) {
		if (ans + log <= N && V[ans + log] <= val) {
			ans += log;
		}
	}

	if (V[ans] == val) {
		return ans;
	}
	else {
		return -1;
	}
}

int bsearch1(int V[], int N, int val) {
	int log;
	for (log = 1; log << 1 <= N; log <<= 1);
	int ans;
	for (ans = 0; log; log >>= 1) {
		if (ans + log <= N && V[ans + log] <= val) {
			ans += log;
		}
	}

	return ans;
}

int bsearch2(int V[], int N, int val) {
	int log;
	for (log = 1; log << 1 <= N; log <<= 1);
	int ans;
	for (ans = N; log; log >>= 1) {
		if (ans - log > 0 && V[ans - log] >= val) {
			ans -= log;
		}
	}

	return ans;
}

int main() {
	fin >> N;
	for (int i = 1; i <= N; ++i) {
		fin >> V[i];
	}
	fin >> T;
	while (T--) {
		int tip, val;
		fin >> tip >> val;
		switch (tip) {
		case 0: {
			fout << bsearch0(V, N, val) << '\n';
			break;
		}
		case 1: {
			fout << bsearch1(V, N, val) << '\n';
			break;
		}
		case 2: {
			fout << bsearch2(V, N, val) << '\n';
			break;
		}
		}
	}

	fout.close();
	return 0;
}