#include<fstream>
using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int a[100001],n,m;
void rez1(int);
void rez2(int);
void rez3(int);
int main()
{	in>>n;
	int op,x;
	for(int i=1;i<=n;i++)
		in>>a[i];
	in>>m;
	for(int i=1;i<=m;i++)
	{	in>>op>>x;
		if(op==0)
			rez1(x);
		else
			if(op==1)
				rez2(x);
			else if(op==2)
				rez3(x);
	}		
	return 0;
}
void rez1(int x)
{	int st,dr,mij,poz=0;
	int ok=0;
	st=1;
	dr=n;
	while(st<=dr)
	{	mij=(st+dr)/2;
		if(x==a[mij])
		{	ok=1;
			if(poz<mij)
				poz=mij;
			st=mij+1;
		}
		else
			if(x<a[mij])
				dr=mij-1;
			else
				st=mij+1;
	}
	if(ok==1)
		out<<poz<<'\n';
	else
		out<<-1<<'\n';
}
void rez2(int x)
{	int st,dr,mij,poz;
	st=1;
	dr=n;
	poz=0;
	while(st<=dr)
	{	mij=(st+dr)/2;
		if(a[mij]<=x)
		{	if(poz<mij)
				poz=mij;
			st=mij+1;
		}	
		else
			dr=mij-1;
	}
	out<<poz<<'\n';
	
}	
void rez3(int x)
{	int st,dr,mij,poz;
	st=1;
	dr=n;
	poz=10000000;
	while(st<=dr)
	{	mij=(st+dr)/2;
		if(a[mij]>=x)
		{	if(poz>mij)
				poz=mij;
			dr=mij-1;
		}
		else
			st=mij+1;
	}
	out<<poz<<'\n';
}