#include <stdio.h>

#define NMAX 100001

int n, m, aux;
int v[NMAX];

int bin_search1(int lo, int hi, int x)
{
	int mid;

	while (lo < hi) {
		mid = (lo + hi) / 2;
		if (v[mid] <= x)
			lo = mid + 1;
		else
			hi = mid - 1;
	}

	mid = (lo + hi) / 2;
	if (v[mid] > x)
		mid--;
	
	return mid;
}

int bin_search2(int lo, int hi, int x)
{
	int mid;

	while (lo < hi) {
		mid = (lo + hi) / 2;
		if (v[mid] < x)
			lo = mid + 1;
		else
			hi = mid - 1;
	}

	mid = (lo + hi) / 2;
	if (v[mid] < x)
		mid++;

	return mid;
}

int main()
{
	// read input
	freopen("cautbin.in", "r", stdin);
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d", &v[i]);

	// do commands
	freopen("cautbin.out", "w", stdout);
	scanf("%d", &m);
	for (int i = 0; i < m; i++) {
		int c, x;
		scanf("%d%d", &c, &x);
		
		switch (c) {
		case 0: aux = bin_search1(1, n, x);
			printf("%d\n", v[aux] == x ? aux : -1);
			break;
		case 1: printf("%d\n", bin_search1(1, n, x));
			break;
		case 2: printf("%d\n", bin_search2(1, n, x));
			break;
		}
	}

	return 0;
}