# include <fstream>
using namespace std;
int main ()
{
	long sir[100001],n,x,m,i,st=1,dr=n,mijl,sol=0,so,ok;
	ifstream f("cautbin.in");
	ofstream g("cautbin.out");
	f>>n;
	for (i=1;i<=n;i++)
		f>>sir[i];
	f>>m;
	for (i=1;i<=m;i++)
	{	ok=0;
		st=1;dr=n;sol=0;
		f>>so>>x;
		if (so==0)
		{	while (st<=dr) {mijl=st+(dr-st)/2;
			if (sir[mijl]==x) {st=mijl+1;sol=mijl;ok=1;}
			else 
				if (sir[mijl]<x) st=mijl+1;
				else dr=mijl-1;}
			if (ok==0) g<<"-1"<<'\n';
			else g<<sol<<'\n';
		}
		else if (so==1)
		{	while (st<=dr) {mijl=st+(dr-st)/2;
			if (sir[mijl]<=x) {st=mijl+1;sol=mijl;}
			else dr=mijl-1;}
			g<<sol<<'\n';
		}
		else
		{	while (st<=dr)
			{	mijl=st+(dr-st)/2;
				if (sir[mijl]>=x) {dr=mijl-1;sol=mijl;}
				else st=mijl+1;
			}
			g<<sol<<'\n';
		}
	}
	f.close ();
	g.close ();
	return 0;
}