#include <cstring>
#include <cstdio>
#include <cmath>

int n, m;
int a[1000001];

int bs0(int trg, int l = 1, int r = n) {
	while (l < r) {
		int p = (l + r) / 2;
		if (trg < a[p]) {
			r = p - 1;
		} else {
			l = p + 1;
		}
	}
	l -= (a[l] > trg);
	return((a[l] == trg) ? l : -1);
}

int bs1(int trg, int l = 1, int r = n) {
	while (l < r) {
		int p = (l + r) / 2;
		if (trg < a[p]) {
			r = p - 1;
		} else {
			l = p + 1;
		}
	}
	return((a[l] <= trg) ? l : l - 1);
}

int bs2(int trg, int l = 1, int r = n) {
	while (l < r) {
		int p = (l + r) / 2;
		if (trg > a[p]) {
			l = p + 1;
		} else {
			r = p - 1;
		}
	}
	return((a[r] >= trg) ? r : r + 1);
}

int main() {
	FILE * in = fopen("cautbin.in", "rt");
	FILE * out = fopen("cautbin.out", "wt");

	fscanf(in, "%d", &n);
	for (int i = 1; i <= n; ++i) {
		fscanf(in, "%d", a + i);
	}
	fscanf(in, "%d", &m);
	while (m--) {
		int x, y, z;
		fscanf(in, "%d%d", &x, &y);
		switch (x) {
			case 0:
				z = bs0(y);
				break;

			case 1:
				z = bs1(y);
				break;

			case 2:
				z = bs2(y);
				break;
		}
		fprintf(out, "%d\n", z);
	}

	fclose(in);
	fclose(out);
}