#include <fstream>
using namespace std;

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

int cautare1(int x, int v[], int n) {
	int left = 1, right = n;
	int sol = -1;
	int mid = (left + right) / 2;
	while (left <= right) {
		mid = (left + right) / 2;
		if (v[mid] <= x) {
			if (v[mid] == x)
				sol = mid;
			left = mid + 1;
		}
		else right = mid - 1;
	}
	return sol;
}

int cautare2(int x, int v[], int n) {
	int left = 1, right = n;
	int sol = -1;
	int mid = (left + right) / 2;
	while (left <= right) {
		mid = (left + right) / 2;
		if (v[mid] <= x) {
			sol = mid;
			left = mid + 1;
		}
		else
			right = mid - 1;
	}
	return sol;
}

int cautare3(int x, int v[], int n) {
	int left = 1, right = n, sol = -1;
	int mid = (left + right) / 2;
	while (left <= right) {
		mid = (left + right) / 2;
		if (v[mid] >= x) {
			sol = mid;
			right = mid - 1;
		}
		else
			left = mid + 1;
	}
	return sol;
}

int n, v[100001], m, x, y;

int main() {
	in >> n;
	for (int i = 1; i <= n; ++i)
		in >> v[i];
	in >> m;
	for (int i = 1; i <= m; ++i) {
		in >> x >> y;
		if (x == 0)
			out << cautare1(y, v, n) << '\n';
		if (x == 1)
			out << cautare2(y, v, n) << '\n';
		if (x == 2)
			out << cautare3(y, v, n) << '\n';
	}
	return 0;
}