#include <stdio.h>
#define NMAX 100002
int n, v[NMAX];

int binarySearchExactElement(int x)
{
	int step, i;
	for (step = 1; step < n; step <<= 1);

	for (i = 0; step; step >>= 1) {
		if (i + step < n && v[i + step] <= x) {
			i += step;
		}
	}

	if (v[i] == x) {
		return i + 1;
	} else {
		return -1;
	}
}

int binarySearchLowerBound(int x)
{
	int step, i;
	for (step = 1; step < n; step <<= 1);

	for (i = 0; step; step >>= 1) {
		if (i + step < n && v[i + step] <= x) {
			i += step;
		}
	}

	return i + 1;
}

int binarySearchUpperBound(int x)
{
	int step, i;
	for (step = 1; step < n; step <<= 1);

	for (i = n - 1; step; step >>= 1) {
		if (i - step >= 0 && v[i - step] >= x) {
			i -= step;
		}
	}

	return i + 1;
}

int main()
{
	FILE *fin, *fout;
	int m, i, type, x;
	fin = fopen("cautbin.in", "r");
	fout = fopen("cautbin.out", "w");
	
	fscanf(fin, "%d", &n);

	for (i = 0; i < n; i++) {
		fscanf(fin, "%d", &v[i]);
	}
	
	fscanf(fin, "%d", &m);
	while (m--) {
		fscanf(fin, "%d %d", &type, &x);
		int answer = 0;
		if (type == 0)
			answer = binarySearchExactElement(x);
		else if (type == 1)
			answer = binarySearchLowerBound(x);
		else
			answer = binarySearchUpperBound(x);

		fprintf(fout, "%d\n", answer);
	}

	fclose(fin);
	fclose(fout);
	return 0;
}