#include <stdio.h>

const int Nmax = 100005;

int n, m;
int a[Nmax];

bool compare1(int x, int y) { return x < y; }

bool compare2(int x, int y) { return x <= y; }

int b_search(int x, bool (*compare)(int, int)) {
	int pos = 0;
	int step = 1 << 16;
	while (step >>= 1)
		if (pos + step <= n && compare(a[pos + step], x))
			pos += step;
	return pos;
}

int main() {
	freopen("cautbin.in", "r", stdin);
	freopen("cautbin.out", "w", stdout);
	int op, x, pos;

	scanf("%d", &n);
	for (int i = 1; i <= n; ++i)
		scanf("%d", &a[i]);

	scanf("%d", &m);
	for (int i = 1; i <= m; ++i) {
		scanf("%d %d", &op, &x);
		if (op == 0) {
			pos = b_search(x, compare2);
			printf("%d\n", ( a[pos] == x ) ? pos : -1);
		}
		else if (op == 1)
			printf("%d\n", b_search(x, compare2));
		else
			printf("%d\n", b_search(x, compare1) + 1);
	}

	return 0;
}