#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int n,m,v[100010],x,limi,lims,mij,ind,i;
int caut0(int x)
{
	limi=1;
	lims=n;
	while (limi<=lims)
	{
		mij=(limi+lims)/2;
		if(v[mij]>x) lims=mij-1;
			else limi=mij+1;
	}
	if (v[mij]>x) mij--;
	if (v[mij]!=x) mij=-1;
	return mij;
}
int caut1(int x)
{
	limi=1;
	lims=n;
	while (limi<=lims)
	{
		mij=(limi+lims)/2;
		if (v[mij]<=x) limi=mij+1;
		else lims=mij-1;
	}
	if (v[mij]>x) mij--;
	return mij;
}
int caut2(int x)
{
	limi=1;
	lims=n;
	while (limi<=lims)
	{
		mij=(limi+lims)/2;
		if (v[mij]>=x) lims=mij-1;
		else limi=mij+1;
	}
	if (v[mij]<x) mij++;
	return mij;
}
int main()
{
	f>>n;
	for (i=1;i<=n;i++)
		f>>v[i];
	f>>m;
	for (i=1;i<=m;i++)
	{
		f>>ind;
		f>>x;
		if (ind==0) g<<caut0(x);
		if (ind==1) g<<caut1(x);
		if (ind==2) g<<caut2(x);
		g<<endl;
	}
	f.close(); g.close();
	return 0;
}