#include<fstream>
using namespace std;
int v[100000],n,m,i,tip,el;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int bs0(int x, int st, int dr)
{
	int m=(st+dr)>>1;
	while(st<=dr){
		m=(st+dr)>>1;
		if(v[m]<=x)
			st=m+1;
		else
			dr=m-1;
	}
	m=(st+dr)>>1;
	if(v[m]>x) --m;
	if(v[m]==x) 
		return m;
	return -1;
}
int bs1(int x, int st, int dr)
{
	int m=(st+dr)>>1;
	while(st<dr){
		m=(st+dr)>>1;
		if(v[m]<=x)
			st=m+1;
		else
			dr=m;
	}
	m=(st+dr)>>1;
	if(v[m]>x) --m;
	return m;
}
int bs2(int x, int st, int dr)
{
	int m=(st+dr)>>1;
	while(st<dr){
		m=(st+dr)>>1;
		if(v[m]<x)
			st=m+1;
		else
			dr=m;
	}
	m=(st+dr)>>1;
	if(v[m]<x)
		++m;
	return m;
}
int main()
{
	in>>n;
	for(i=1;i<=n;i++)
		in>>v[i];
	for(in>>m;m;--m){
		in>>tip>>el;
		if(tip==0)
			out<<bs0(el,1,n);
		if(tip==1)
			out<<bs1(el,1,n);
		if(tip==2)
			out<<bs2(el,1,n);
	}
	return 0;
}