//Cautare binara - Arhiva educationala(Ideea lui Mihai Patrascu)
#include <stdio.h>
#define INPUT "cautbin.in"
#define OUTPUT "cautbin.out"
#define NMAX 131072
int N, M;

int v[NMAX];

int caut_bin(int val)
{
	int i, step;
	for(step = 1; step < N; step <<= 1);
	
	for(i = 0; step; step >>= 1)
		if(i + step <= N && v[i + step] <= val)
			i += step;
	
	return i;
}

int caut_bin2(int val)
{
	int i, step;
	for(step = 1; step < N; step <<= 1);
	
	for(i = 0; step; step >>= 1)
		if(i + step <= N && v[i + step] < val)
			i += step;
	
	return i+1;
}

int main()
{
	freopen(INPUT, "r", stdin);
	freopen(OUTPUT, "w", stdout);
	
	scanf("%d", &N);
	int i;
	for(i = 1; i <= N; ++i)
		scanf("%d", v+i);
	
	scanf("%d", &M);
	for(i = 1;  i <= M; ++i)
	{
		int tip, val;
		scanf("%d %d", &tip, &val);
		
		int rez;
		if(tip < 2)
		{
			rez = caut_bin(val);
			if(tip == 0)
			{
				if(v[rez] != val) rez = -1;
			}
		}
		else if(tip == 2) rez = caut_bin2(val);
		
		printf("%d\n", rez);
	}
	
	return 0;
}