#include<iostream>
#include<fstream>
using namespace std; 
long int n, x[100001], val1, m, res;
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=st+(dr-st)/2;
	if(x[mij]==val)
		poz=mij;
	if(val<x[mij])
		dr=mij-1;
	else
		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-st)/2;
	if(x[mij]==val)
		{
		poz=mij;
		st=mij+1;
		}
	else
	if(val<x[mij])
		dr=mij-1;
	else
		st=mij+1;
	}
if(poz==-1)
	return st-1;
else
	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=st+(dr-st)/2;
	if(x[mij]==val)
		{
		poz=mij;
		dr=mij-1;
		}
	else
	if(val<x[mij])
		dr=mij-1;
	else
		st=mij+1;
	}
if(poz==-1)
	{
	return st+1;
	}
else
	return poz;
}

int main(){
	ifstream f1("cautbin.in");
	f1>>n;
	for(long int i=1; i<=n; i++)
		f1>>x[i];
	f1>>m;long int cond1;
	ofstream f2("cautbin.out");
	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();
	return 0;
}