#include <fstream>
using namespace std;

int main()
{
long a[100001],n,x,gasit,dr,st,i,mijloc,poz,gata,m,nr;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
in>>n;
for(i=1;i<=n;i++)
	in>>a[i];
in>>m;
for(i=1;i<=m;i++)
{
	in>>nr>>x;
	if(nr==0)
	{
		for(st=1,dr=n,gata=0;!gata && st<=dr;)
		{
			mijloc=(st+dr)/2;
			if(a[mijloc]==x)
			{
				gata=1;
				poz=mijloc;
			}
		else if(a[mijloc]<x)
			st=mijloc+1;
		else
			dr=mijloc-1;
	}
	if(gata)
		out<<poz<<"\n";
	else
		out<<-1<<"\n";
	} //1

	else if(nr==1)
	{
		for(st=1,dr=n,gata=0;st<=dr;)
		{
			mijloc=(st+dr)/2;
			if(a[mijloc]<=x)
			{
				poz=mijloc;
				st=mijloc+1;
			}
			else
				dr=mijloc-1;
		}
		out<<poz<<"\n";
	} //2

	else
	{
		for(st=1,dr=n,gata=0;st<=dr;)
		{
			mijloc=(st+dr)/2;
			if(a[mijloc]>=x)
			{
				poz=mijloc;
				dr=mijloc-1;
				
			}
			else
				st=mijloc+1;
		}
		out<<poz<<"\n";
	}//3

}

return 0;
}