#include <stdio.h>

#define MAX_N 100000

int cautareBinara0(int v[], int len, int val) {
	int low_bound  = 0, high_bound = len - 1;
	int mid;
	while (low_bound <= high_bound) {
		mid = (low_bound + high_bound) / 2;
		if (v[mid] <= val)
			low_bound = mid + 1;
		else
			high_bound = mid - 1;
	}
	mid = (low_bound + high_bound) / 2;
	if (v[mid] > val)
		mid--;

	return v[mid] == val ? mid : (-1);
}

int cautareBinara1(int v[], int len, int val) {
	int low = 0, hi = len - 1;
	int mid;
	while (low <= hi) {
		mid = (low + hi) / 2;
		if (v[mid] <= val)
			low = mid + 1;
		else
			hi = mid - 1;
	}
	mid = (low + hi) / 2;
	if (v[mid] > val)
		mid--;

	return mid;
}

int cautareBinara2(int v[], int len, int val) {
	int low = 0, hi = len - 1;
	int mid;
	while (low <= hi) {
		mid = (low + hi) / 2;
		if (v[mid] < val)
			low = mid + 1;
		else
			hi = mid - 1;
	}
	mid = (low + hi) / 2;
	if (v[mid] < val)
		mid++;

	return mid;
}

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

	int n, m, i, tip_cautare, nr_cautat, v[MAX_N], x;

	fscanf(in, "%d", &n);
	for (i = 0; i < n; i++)
		fscanf(in, "%d", &v[i]);
	fscanf(in, "%d", &m);
	for (i = 0; i < m; i++) {
		fscanf(in, "%d %d", &tip_cautare, &nr_cautat);
		switch (tip_cautare) {
			case 0:
				x = cautareBinara0(v, n, nr_cautat);
				if (x != -1)
					x++;
				fprintf(out, "%d\n", x);
				break;
			case 1:
				fprintf(out, "%d\n", cautareBinara1(v, n, nr_cautat) + 1);
				break;
			case 2:
				fprintf(out, "%d\n", cautareBinara2(v, n, nr_cautat) + 1);
				break;
		}
	}

	fclose(in);
	fclose(out);

	return 0;
}