#include <stdio.h>
#include <math.h>

long poz1, poz2, x, n, m, choice, a[100010], i;

long bin1() {
	long sol = 0;
	while (poz1 < poz2) {
		if (a[(poz1 + poz2) / 2] > x) {
			poz2 = (poz1 + poz2) / 2;
			continue;
		}
		if (a[(poz1 + poz2) / 2] < x) {
			poz1 = (poz1 + poz2) / 2 + 1;
			continue;
		}
		if (a[(poz1 + poz2) / 2] == x) {
			sol = (poz1 + poz2) / 2;
			poz1 = sol + 1;
		}
	}
	return sol;
}

long bin2() {
	long sol = 0;
	while (poz1 < poz2) {
		if (a[(poz1 + poz2) / 2] > x) {
			poz2 = (poz1 + poz2) / 2;
			continue;
		}
		if (a[(poz1 + poz2) / 2] <= x) {
			sol = (poz1 + poz2) / 2;
			poz1 = sol + 1;
			continue;
		}
	}
	return sol;
}

long bin3() {
	long sol = 0;
	while (poz1 < poz2) {
		if (a[(poz1 + poz2) / 2] >= x) {
			sol = (poz1 + poz2) / 2;
			poz2 = sol - 1;
			continue;
		}
		if (a[(poz1 + poz2) / 2] < x) {
			poz1 = (poz1 + poz2) / 2;
			continue;
		}
	}
	return sol;
}

int main() {
	freopen("cautbin.in", "r", stdin);
	freopen("cautbin.out", "w", stdout);
	scanf("%ld", &n);
	for (i = 1; i <= n; ++i) {
		scanf("%ld", &a[i]);
	}
	scanf("%ld", &m);
	for (i = 1; i <= m; ++i) {
		scanf("%ld", &choice);
		scanf("%ld", &x);
		if (choice == 0) {
			poz1 = 1; 
			poz2 = n;
			if (bin1() == 0) {
				printf("-1");
			} else {
				poz1 = 1;
				poz2 = n;
				printf("%ld\n", bin1());
			}
		}
		if (choice == 1) {
			poz1 = 1;
			poz2 = n;
			printf("%ld\n", bin2());
		}
		if (choice == 2) {
			poz1 = 1;
			poz2 = n;
			printf("%ld\n", bin3());
		}
	}
	return 0;
}