#include <fstream>
using namespace std;

int n,m,i,v[101000],tip,x;

int cautare0(int x) 
{
	int p,u,m,poz;
	p=1;
	u=1;
	poz=-1;
	while(p<=u)
	{
		m=(p+u)/2;
		if(x==v[m])
		{
			poz=m;
			p=m+1;
		} 
		else
		if(x<v[m])
		   u=m-1;
	    else
		   p=m+1;
	}
	
	return poz;
}

int cautare1(int x)
{
	int p,u,m,poz;
	p=1;
	u=n;
	poz=1;
	
	while(p<=u)
	{
		m=(p+u)/2;
		if(x>=v[m])
		{
			poz=m;
			p=m+1;
		} 
		else 
			u=m-1;
	}
	
	return poz;
}

int cautare2(int x)
{
	int p,u,m,poz;
	p=1;
	u=n;
	poz=1;
	while(p<=u)
	{
		m=(p+u)/2;
		if(x<=v[m])
		{
			poz=m;
			u=m-1;
		}
		else
			p=m+1;
	}
	
	return poz;
}

int main()
{
	ifstream f("cautbin.in");
	ofstream g("cautbin.out");
	
	f>>n;
	for (i=1;i<=n;i++)
		 f>>v[i];
	f>>m;
	for (i=1;i<=m;i++)
	{
		f>>tip; f>>x;
		if (tip==0)
			g<<cautare0(x)<<"\n";
		if (tip==1)
			g<<cautare1(x)<<"\n";
		if (tip==2)
			g<<cautare2(x)<<"\n";
	}
	
	return 0;
}