#include <stdio.h>

#define N 100000
#define M 100000

FILE* in;
FILE* out;
int a[N];
int n;

int find(int code, int x) {
	int lo = -1, hi = n;
	while (hi - lo > 1) {
		int mid = lo + (hi - lo) / 2;
		if (code == 0 || code == 1)
			if (a[mid] <= x)
				lo = mid;
			else
				hi = mid;
		else
			if (a[mid] < x)
				lo = mid;
			else
				hi = mid;
	}
	if (code == 0) {
		if (lo == -1 || a[lo] != x) {
			return -1;
		}
		return lo + 1;
	}
	if (code == 1) {
		return lo + 1;
	}
	if (code == 2) {
		return hi + 1;
	}
	return 0;
}

int main() {
	in = fopen("cautbin.in", "r");
	out = fopen("cautbin.out", "w");
	fscanf(in, "%d", &n);
	int i;
	for (i = 0; i < n; ++i)
		fscanf(in, "%d", a + i);
	int m;
	fscanf(in, "%d", &m);
	for (i = 0; i < m; ++i) {
		int code, x;
		fscanf(in, "%d", &code);
		fscanf(in, "%d", &x);
		fprintf(out, "%d\n", find(code, x));
	}
	return 0;
}