#include<iostream>
#include<fstream>
using namespace std; 
long int n, x[100001], val1, m, res,i;
ifstream f1("cautbin.in");
ofstream f2("cautbin.out");
long int caut_bin0(long int val)
{
long int st=1, dr=n, poz=-1, mij;
while(st<=dr)
	{
	mij=(dr+st)/2;
	if(x[mij]==val)
	{poz=mij;st=mij+1;}
	if(val<x[mij])
		dr=mij-1;
	else
		st=mij+1;
	}
return poz;
}

long int caut_bin2(long int val)
{
long int st=1, dr=n, poz=-1, mij;
while(st<=dr)
	{
	mij=(dr+st)/2;
	if(x[mij]>=val)
	{dr=mij-1;poz=mij;}
	if(x[mij]<val)
		st=mij+1;
	}
	return poz;
}

long int caut_bin1(long int val)
{
long int st=1, dr=n, poz=-1, mij;
while(st<=dr)
	{
	mij=(st+dr)/2;
	if(x[mij]<=val)
	{st=mij+1;poz=mij;}
	if(x[mij]>val)
		dr=mij-1;
	}
	return poz;
}

int main(){

	f1>>n;
	for(i=1; i<=n; i++)
		f1>>x[i];
	f1>>m;
	long int cond1;
	while(m--)
		{
		f1>>cond1;
		f1>>val1;
		if(cond1==0)
			f2<<caut_bin0(val1)<<endl;
		if(cond1==1)
			f2<<caut_bin1(val1)<<endl;
		if(cond1==2)
			f2<<caut_bin2(val1)<<endl;
		}
return 0;
}