#include <stdio.h>

#define MAXN 100000

int n, v[MAXN + 1];
int p2;

int op0(int x)
{
	int step, index = 0;
	for(step = p2; step; step /= 2)
		if(index + step <= n && v[index + step] <= x)
			index += step;
	if(v[index] == x) return index;
	return -1;
}

int op1(int x)
{
	int step, index = 0;
	for(step = p2; step; step /= 2)
		if(index + step <= n && v[index + step] <= x)
			index += step;
	return index;
}

int op2(int x)
{
	int step, index = n;
	for(step = p2; step; step /= 2)
		if(index - step > 0 && v[index - step] >= x)
			index -= step;
	return index;
}

int main()
{
	freopen("cautbin.in", "r", stdin);
	freopen("cautbin.out", "w", stdout);
	
	scanf("%d", &n);
	for(p2 = 1; p2 <= n; p2 *= 2);
	p2 /= 2;
	fprintf(stderr, "p2 = %d\n", p2);

	int i;	
	for(i = 1; i <= n; ++i) scanf("%d", &v[i]); //am citit sirul
	
	int m;
	scanf("%d", &m); //numar de operatii
	
	int codOP, x;
	while(m--)
	{
		//pentru fiecare operatie
		scanf("%d%d", &codOP, &x);
		if(codOP == 0) printf("%d\n", op0(x));
		else if(codOP == 1) printf("%d\n", op1(x));
		else printf("%d\n", op2(x));
	}

	return 0;
}