#include<iostream>
#include<fstream>
using namespace std; 
long int n, x[100001], val1, m, res;
ifstream f1("cautbin.in");
ofstream f2("cautbin.out");
long int caut_bin0(long int val)
{
long int st=1;
long int dr=n;
long int poz=-1;
while(st<=dr)
	{
	long int mij;
	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;
long int dr=n;
long int poz=-1;
while(st<=dr)
	{long int mij;
	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;
long int dr=n;
long int poz=-1;
while(st<=dr)
	{long int mij;
	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(long int i=1; i<=n; i++)
		f1>>x[i];
	f1>>m;
	long int cond1;
	for(long int i=1; i<=m; i++)
		{
		f1>>cond1;
		f1>>val1;
		if(cond1==0)
			f2<<caut_bin0(val1)<<endl;
		else
			if(cond1==1)
				f2<<caut_bin1(val1)<<endl;
			else
				f2<<caut_bin2(val1)<<endl;
		}
	f1.close();	
	f2.close();
}