#include<fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int v[100001];

int caut0(int prim,int ult,int key)
{
	int mij;
	while(prim<=ult)
	{
		mij=(prim+ult)/2;
		if(v[mij]<=key)
			prim=mij+1;
		else ult=mij-1;
	}
	mij=(prim+ult)/2;
	if(v[mij]>key) mij--;
	if(v[mij]==key)
		return mij;
	return -1;
}
	
int caut1(int prim,int ult,int key)
{
	int mij;
	while(prim<ult)
	{
		mij=(prim+ult)/2;
		if(v[mij]<=key)
			prim=mij+1;
		else ult=mij;
	}
	mij=(prim+ult)/2;
	if(v[mij]>key) mij--;
	return mij;

}

int caut2(int prim,int ult,int key)
{
	int mij;
	while(prim<ult)
	{
		mij=(prim+ult)/2;
		if(v[mij]<key)
			prim=mij+1;
		else ult=mij;
	}
	mij=(prim+ult)/2;
	if(v[mij]<key) mij++;
	return mij;
}

int main()
{
	int i,n,m,tip,x;
	f>>n;
	for(i=1;i<=n;i++)
		f>>v[i];
	f>>m;
	for(i=1;i<=m;i++)
	{
		f>>tip>>x;
		if(tip==0)
			g<<caut0(1,n,x)<<'\n';
		if(tip==1)
			g<<caut1(1,n,x)<<'\n';
		if(tip==2)
			g<<caut2(1,n,x)<<'\n';
	}
	f.close();
	g.close();
	return 0;
}