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

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

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=sarc0(crt);
			if (poz0) printf("%d\n", poz0);
			else printf("-1\n");
		}
		else if (sarc==1)
		{
			sarc1(1,N,crt);
			printf("%d\n", poz0);
		}
		else
		{
			sarc2(1,N,crt);
			printf("%d\n", poz0);
		}
	}
	return 0;
}