#include <fstream>
using namespace std;

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

int cautareBinara0(int x, int v[], int n) {
	int lo = 1, hi = n;
	int sol = -1;
	while (lo <= hi) {
		int mid = lo + (hi - lo) / 2;
		if (v[mid] == x) {
			sol = mid;
		}
		if (v[mid] <= x) {
			lo = mid + 1;
		}
		if (v[mid] > x) {
			hi = mid - 1;
		}
	}
	return sol;
}

int cautareBinara1(int x, int v[], int n) {
	int lo = 1, hi = n;
	int sol = -1;
	while (lo <= hi) {
		int mid = lo + (hi - lo) / 2;
		if (v[mid] <= x) {
			sol = mid;
		}
		if (v[mid] <= x) {
			lo = mid + 1;
		}
		if (v[mid] > x) {
			hi = mid - 1;
		}
	}
	return sol;
}

int cautareBinara2(int x, int v[], int n) {
	int lo = 1, hi = n;
	int sol = -1;
	while (lo <= hi) {
		int mid = lo + (hi - lo) / 2;
		if (v[mid] <= x) {
			sol = mid;
		}
		if (v[mid] < x) {
			lo = mid + 1;
		}
		if (v[mid] >= x) {
			hi = mid - 1;
		}
	}
	return sol;
}

int v[100002];
int n, m, x, y;
int main() {
	fin >> n;
	for (int i = 1; i <= n; ++i)
		fin >> v[i];
	fin >> m;
	for (int i = 1; i <= m; ++i) {
		fin >> x >> y;
		if (x == 0)
			fout << cautareBinara0(y, v, n) << '\n';
		if (x == 1)
			fout << cautareBinara1(y, v, n) << '\n';
		if (x == 2)
			fout << cautareBinara2(y, v, n) << '\n';
	}
}