#include <stdio.h>
#include <stdlib.h>

int bsrc0(int x, int *a, int low, int high)
{
	int mid = low + (high - low) / 2;

	fprintf(stderr, "%i %i %i\n", low, mid, high);

	if (low + 1 == high)
		if (a[low] == x)
			return low + 1;
		else
			return -1;

	if (low >= high)
		return -1;

	if (a[mid] <= x)
		low = mid;
	else if (a[mid] > x)
		high = mid;

	return bsrc0(x, a, low, high);
}

int bsrc1(int x, int *a, int low, int high)
{
	int mid = low + (high - low) / 2;

	fprintf(stderr, "%i %i %i\n", low, mid, high);

	if (low + 1 == high)
		return low + 1;

	if (low >= high)
		return -1;

	if (a[mid] <= x)
		low = mid;
	else
		high = mid;

	return bsrc1(x, a, low, high);
}


int bsrc2(int x, int *a, int low, int high)
{
	int mid = high - (high - low) / 2;

	fprintf(stderr, "%i %i %i\n", low, mid, high);

	if (low + 1 == high)
		return high + 1;

	if (low >= high)
		return -1;

	if (a[mid] < x)
		low = mid;
	else
		high = mid;

	return bsrc2(x, a, low, high);
}

int main(void)
{
	int n, m, *a, i;


	if (!freopen("cautbin.in", "r", stdin) ||
	    !freopen("cautbin.out", "w", stdout))
		exit(1);


	scanf("%i", &n);
	a = malloc(n * sizeof(*a));
	if (!a)
		exit(2);

	for (i = 0; i < n; i++)
		scanf("%i ", a + i);

	scanf("%i", &m);

	for (i = 0; i < m; i++) {
		int type, x, pos;

		scanf("%i %i", &type, &x);
		switch (type) {
		case 0:
			pos = bsrc0(x, a, 0, n);
			break;
		case 1:
			pos = bsrc1(x, a, 0, n);
			break;
		case 2:
			pos = bsrc2(x, a, -1, n - 1);
			break;
		default:
			pos = -1;
			break;
		}
		printf("%i\n", pos);
	}

	free(a);

	return 0;
}