#include<fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int v[100001],n;
int bin0(int i,int j,int x)
{	int m;
	while(i<=j)
	{
		m=(i+j)/2;
		if(v[m]<=x)
			i=m+1;
		else j=m-1;
	}
	if(v[i]==x)return i;
	else if(v[j]==x) return j;
			else return -1;
}
int bin1(int i,int j,int x)
{
	int m;
	while(i<=j)
	{
		m=(i+j)/2;
		if(v[m]<=x)
			i=m+1;
		else j=m-1;
	}
	if(v[j]<=x)return j;
	else return i;
}
int bin2(int i,int j,int x)
{
	int m;
	while(i<=j)
	{
		m=(i+j)/2;
		if(v[m]<x)
			i=m+1;
		else j=m-1;
	}
	if(v[j]>=x)return j;
		else return i;
}
void solve(int cer,int x)
{
	if(cer==0)
		g<<bin0(1,n,x)<<'\n';
	else
		if(cer==1)
			g<<bin1(1,n,x)<<'\n';
		else g<<bin2(1,n,x)<<'\n';
}
int main()
{ int x,cer,m,i;
	f>>n;
	for(i=1;i<=n;i++)
		f>>v[i];
	f>>m;
	for(i=1;i<=m;i++)
	{	f>>cer>>x;
		solve(cer,x);
	}
	
	return 0;
}