#include<fstream>
using namespace std;
int n,x[100010];

int cb1(int val)
{
	int st,p,med,last=-1;
	st=1;p=n;
	while(st<=p)
	{
		med=(st+p)/2;
		if(val>=x[med])
		{
			last=med;
			st=med+1;
		}
		else p=med-1;
	}
	return last;
}
int cb3(int val)
{
	int st,p,med,last=-1;
	st=1;p=n;
	while(st<=p)
	{
		med=(st+p)/2;
		if(val<=x[med])
		{
			last=med;
			p=med-1;
		}
		else st=med+1;
	}
	return last;
}

int main()
{
	ifstream f("cautbin.in");
	ofstream g("cautbin.out");
	int m,a,b,i,poz;
	f>>n;
	for(i=1;i<=n;i++) f>>x[i];
	f>>m;
	for(i=1;i<=m;i++)
	{
		f>>a>>b;
		poz=cb1(b);
		if(a==0)
			if (x[poz]==b) g<<poz<<'\n';
		    else g<<-1<<'\n';
		else if(a==1) g<<poz<<'\n';
		else g<<cb3(b)<<'\n';
	}
	f.close();
	g.close();
	return 0;
}