#include<fstream.h>
#define MAX 100001

long n,m,a[MAX],x,poz;
int op;
ofstream fout("cautbin.out");



void bin(long st, long dr)
{
	long mij;
	if(st<=dr)
		{
			mij=st+(dr-st)/2;
			if(a[mij]==x)
				poz=mij;
			 else
				 if(a[mij]>x)
							bin(st,mij-1);
					else
						bin(mij+1,dr);
		}
}


void bin1(long st, long dr)
{
	long mij;
	if(st<=dr)
		{
			mij=st+(dr-st)/2;
			if(a[mij]<=x)
				poz=mij, bin1(mij+1,dr);
			 else
				 bin1(st,mij-1);
		}
}




void bin2(long st, long dr)
{
	long mij;
	if(st<=dr)
		{
			mij=st+(dr-st)/2;
			if(a[mij]>=x)
				poz=mij, bin2(st,mij-1);
			 else
				 bin2(mij+1,dr);
		}
}




void citire()
{
	ifstream fin("cautbin.in");
	long i;
	fin>>n;
	for(i=1;i<=n;i++)
		fin>>a[i];
	fin>>m;
	for(i=1;i<=m;i++)
		{
			fin>>op>>x;
			poz=0;
			if (op==0) bin(1,n);
				else if (op==1) bin1(1,n);
					else bin2(1,n);
			if (poz==0) fout<<"-1"<<'\n';
				else fout<<poz<<'\n';
		}
}


int main()
{
	citire();
	fout.close();
	return 0;
}