#include <stdio.h>
#define Nmax 100001
int sir[Nmax];
long i,N,M,sarc,crt,poz0;

int sarc0 (long l, long r, long x)
{
	//cea mai mare pozitie pe care se afla un element cu valoarea x sau -1 
	//daca aceasta valoare nu se gaseste in sir
	if (l>r) return poz0;
	else 
	{
		long m; m=(l+r)/2;
		if (sir[m]==x) { poz0=m; sarc0(m+1,r,x);}
		else if (x<sir[m]) sarc0(l,m-1,x);
		else sarc0(m+1,r,x);
	}
}

int sarc1 (long l, long r, long x)
{
	//cea mai mare pozitie pe care se afla un element cu valoarea mai mica 
	//sau egala cu x in sir. Se garanteaza ca cel mai mic numar al sirului este mai mic 
	//sau egal decat x 
	if (l>r) return poz0;
	else 
	{
		long m; m=(l+r)/2;
		if (sir[m]<=x) { poz0=m; sarc1(m+1,r,x);}
		else sarc1(l,m-1,x);
	}
}

int sarc2 (long l, long r, long x)
{
	//cea mai mica pozitie pe care se afla un element cu valoarea mai mare 
	//sau egala cu x in sir. Se garanteaza ca cel mai mare numar din sir este mai mare 
	//sau egal decat x
	if (l>r) return poz0;
	else 
	{
		long m; m=(l+r)/2;
		if (sir[m]>=x) { poz0=m; sarc2(l,m-1,x);}
		else sarc2(m+1,r,x);
	}
}

int main () {
	freopen("cautbin.in", "r", stdin);
	freopen("cautbin.out", "w", stdout);
	scanf("%d", &N);
	for (i=1; i<=N; i++) scanf("%d", &sir[i]);
	scanf("%d", &M);
	for (i=1; i<=M; i++)
	{
		scanf("%d %d", &sarc, &crt);
		if (sarc==0)
		{
			poz0=-1;
			sarc0(1,N,crt);
			printf("%d\n", poz0);
		}
		else if (sarc==1)
		{
			sarc1(1,N,crt);
			printf("%d\n", poz0);
		}
		else
		{
			sarc2(1,N,crt);
			printf("%d\n", poz0);
		}
	}
	return 0;
}