#include <cstdio>

const int NMAX = 100005;
int V[NMAX];

/* Varianta clasica recursiva. Nu merge in acest caz deoarece trebuie de pe
 * pozitia cea mai mare - pt operatia 0. */
int binary_search(int lo, int hi, int key)
{
	if (hi < lo)
		return -1;

	int mid = lo + (hi - lo) >> 1;

	if (key < V[mid])
		binary_search(lo, mid - 1, key);
	else if (key > V[mid])
		binary_search(mid + 1, hi, key);
	else
		return mid;
}

int bsearch0(int lo, int hi, int key)
{
	int mid;

	while (lo <= hi) {
		mid = lo + ((hi - lo) >> 1);

		if (V[mid] <= key)
			lo = mid + 1;
		else
			hi = mid - 1;
	}

	return (lo + hi) >> 1;
}

int bsearch1(int lo, int hi, int key)
{
	int mid;

	while (lo < hi) {
		mid = lo + ((hi - lo) >> 1);

		if (V[mid] < key)
			lo = mid + 1;
		else
			hi = mid;
	}

	return lo;
}

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

	int N, M;
	int i;

	scanf("%d", &N);
	for (i = 0; i < N; ++i)
		scanf("%d", &V[i]);

	scanf("%d", &M);
	for (; M; --M) {
		int type, x;
		int ret;

		scanf("%d %d", &type, &x);
		if (!type || type == 1) {
			ret = bsearch0(0, N - 1, x);

			if (!type && V[ret] != x)
				printf("-1\n");
			else
				printf("%d\n", ret + 1);
		} else {
			printf("%d\n", bsearch1(0, N - 1, x) + 1);
		}
	}

	return 0;
}