#include<cstdio>
using namespace std;

int n, v[100005];

int caut0(int x) {
	int poz = -1, mij, lo = 0, hi = n-1;
	while (lo <= hi) {
		mij = lo + (hi - lo) / 2;
		if (x > v[mij]) {
			hi = mij - 1;
		} else {
			if (x < v[mij]) {
				lo = mij + 1;
			} else {
				poz = mij;
				lo = mij + 1;
			}
		}
	}
	return (poz == -1) ? poz : poz + 1;
}

int caut1(int x) {
	int poz = -1, mij, lo = 0, hi = n-1;
	while (lo <= hi) {
		mij = lo + (hi - lo) / 2;
		if (v[mij] > x) {
			hi = mij - 1;
		} else {
			poz = mij;
			lo = mij + 1;
		}
	}
	return poz;
}

int caut2(int x) {
	int poz = -1, mij, lo = 0, hi = n-1;
	while (lo <= hi) {
		mij = lo + (hi - lo) / 2;
		if (v[mij] < x) {
			lo = mij + 1;
		} else {
			poz = mij;
			hi = mij - 1;
		}
	}
	return poz;
}

int main() {
	freopen("cautbin.in", "r", stdin);
	freopen("cautbin.out", "w", stdout);
	int m, i, type, x;
	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%d", v + i);
	}
	scanf("%d", &m);
	for (i = 0; i < m; i++) {
		scanf("%d %d", &type, &x);
		if (type == 0) printf("%d\n", caut0(x));
		if (type == 1) printf("%d\n", caut1(x) + 1);
		if (type == 2) printf("%d\n", caut2(x) + 1);
	}
	return 0;
}