#include <stdio.h>

int v[100000];

int bsearch(int x, int l, int u) {
	int i;

	for (i = 0; (1<<i) <= u; ++i)
		;
	for (; i >= 0; --i)
		if ((l + (1<<i) <= u) && (v[l + (1<<i)] <= x))
			l += 1<<i;
	return ((v[l] == x) ? (l) : (-2));
}

int bsearchl(int x, int l, int u) {
	int i;

	for (i = 0; (1<<i) <= u; ++i)
		;
	for (; i >= 0; --i)
		if ((l + (1<<i) <= u) && (v[l + (1<<i)] < x))
			l += 1<<i;
	return ((v[l+1] != x) ? (l) : (l+1));
}

int bsearchu(int x, int l, int u) {
	int i;

	for (i = 0; (1<<i) <= u; ++i)
		;
	for (; i >= 0; --i)
		if ((l + (1<<i) <= u) && (v[l + (1<<i)] <= x))
			l += 1<<i;
	return ((v[l] != x) ? (l+1) : (l));
}

int main(int argc, char *argv[]) {
	int N, i, M, op, x;

	FILE *fi = fopen("cautbin.in", "r");
	fscanf(fi, "%d", &N);
	for (i = 0; i < N; ++i)
		fscanf(fi, "%d", v+i);
	fscanf(fi, "%d", &M);
	FILE *fo = fopen("cautbin.out", "w");
	while (M--) {
		fscanf(fi, "%d %d", &op, &x);
		switch (op) {
			case 0:
				fprintf(fo, "%d\n", bsearch(x, 0, N-1)+1);
				break;
			case 1:
				fprintf(fo, "%d\n", bsearchl(x, 0, N-1)+1);
				break;
			case 2:
				fprintf(fo, "%d\n", bsearchu(x, 0, N-1)+1);
				break;
		};
	}
	fclose(fo);
	fclose(fi);

	return 0;
}