// Binary_search.cpp : Defines the entry point for the console application.
//

#include <stdio.h>
#define maxn 100005

int Upper_bound(int n, int val, int V[]) {
	int left = 0, right = n - 1, mid, pos;
	while (left <= right) {
		mid = (left + right) >> 1;
		if (V[mid] <= val) {
			pos = mid;
			left = mid + 1;
		} else {
			right = mid - 1;
		}
	}
	return pos;
}

int Lower_bound(int n, int val, int V[]) {
	int left = 0, right = n - 1, mid, pos;
	while (left <= right) {
		mid = (left + right) >> 1;
		if (V[mid] < val) {
			left = mid + 1;
		} else {
			pos = mid;
			right = mid - 1;
		}
	}
	return pos;
}

int main() {
	FILE *fin = fopen("cautbin.in", "r");
	FILE *fout = fopen("cautbin.out", "w");
	int V[maxn], n, m, type, i, x, pos;
	fscanf(fin, "%d", &n);
	for (i = 0; i < n; i++) {
		fscanf(fin, "%d", &V[i]);
	}
	fscanf(fin, "%d", &m);
	for (i = 0; i < m; i++) {
		fscanf(fin, "%d %d", &type, &x);
		if (type == 0) {
			pos = Upper_bound(n, x, V);
			if (V[pos] != x) {
				fprintf(fout, "-1 \n");
			} else {
				fprintf(fout, "%d \n", pos + 1);
			}
		} else if (type == 1) {
			pos = Upper_bound(n, x, V);
			fprintf(fout, "%d\n", pos + 1);
		}	else {
			pos = Lower_bound(n, x, V);
			fprintf(fout, "%d\n", pos + 1);
		}
	}
	fclose(fin);
	fclose(fout);
    return 0;
}