#include<fstream>
using namespace std;
int v[100000];
int binara0(int p,int u,int val)
{
	int m;
	while(p<=u)
	{
		m=(p+u)/2;
		if(v[m]>val)
			u=m-1;
		else p=m+1;
	}
	m=(p+u)/2;
	if(v[m]>val) m--;
	if(v[m]==val) return m;
	return -1;
}
int binara1(int p,int u,int val)
{
	int m;
	while(p<u)
	{
		m=(p+u)/2;
		if(v[m]>val)
			u=m;
		else
			p=m+1;
	}
	m=(p+u)/2;
	if(v[m]>val) m--;
	return m;
}
int binara2(int p,int u,int val)
{
	int m;
	while(p<u)
	{
		m=(p+u)/2;
		if(v[m]>=val)
			u=m;
		else
			p=m+1;
	}
	m=(p+u)/2;
	if(v[m]<val)
		m++;
	return m;
}
int main()
{
	int n,i,y,t,x;
	ifstream f("cautbin.in");
	ofstream g("cautbin.out");
	f>>n;
	for(i=1;i<=n;i++)
		f>>v[i];
	f>>y;
	for(i=1;i<=y;i++)
	{
		f>>t>>x;
		if(t==0)
			g<<binara0(1,n,x)<<endl;
		if(t==1)
			g<<binara1(1,n,x)<<endl;
		if(t==2)
			g<<binara2(1,n,x)<<endl;
	}
	return 0;
}