#include<fstream.h>
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int a[100001],n,i,j,x,m;
void cautx(long i,long j)
{long m;
	m=i+(j-i)/2;
	if (x==a[m]) {fout<<m<<'\n'; return;}
	if (i==j) {fout<<-1<<'\n';return;}
	if (x!=a[m] && i!=j)
		{if (x>a[m]) cautx(m+1,j);
		 if (x<a[m]) cautx(i,m-1);}
	}
void cautmin(long i,long j)
{long m;
	m=i+(j-i)/2;
	if (x>=a[m] && x<a[m+1]) {fout<<m<<'\n'; return;}
	else
		{if (x>a[m]) cautmin(m+1,j);
		 if (x<a[m]) cautmin(i,m-1);}
	}
void cautmax(long i,long j)
{long m;
	m=i+(j-i)/2;
	if (x<=a[m] && x>a[m-1]) {fout<<m<<'\n'; return;}
	else
		{if (x>a[m]) cautmax(m+1,j);
		 if (x<a[m]) cautmax(i,m-1);}
	}
int s;
int main()
	{long k;
	 fin>>n;
	 for (i=1;i<=n;i++)
		fin>>a[i];
	 fin>>m;
	 for (k=1;k<=m;k++)
	 {fin>>s>>x;
		if (s==0) cautx(1,n);
		if (s==1) cautmin(1,n);
		if (s==2) cautmax(1,n);}
fout.close();
return 0;}