#include<fstream>

using namespace std;

ifstream cin("cautbin.in");
ofstream cout("cautbin.out");

int n,a[100005],m,i,q,nr,st,dr,mid;
 
int cautbin1(int val)
{
	st=1;
	dr=n;
	while(st<=dr)
	{
	mid=(st+dr)/2;
	if(a[mid]<=val)st=mid+1;
	else dr=mid-1;
	}
	mid=(st+dr)/2;
	if(a[mid]>val)--mid;
	if(a[mid]==val)return mid;
	else return -1;
}

int cautbin2(int val)
{
	st=1;
	dr=n;
	while(st<dr)
	{
	mid=(st+dr)/2;
	if(a[mid]<=val)st=mid+1;
	else dr=mid-1;
	}
	mid=(st+dr)/2;
	if(a[mid]>val)--mid;
	return mid;
}

int cautbin3(int val)
{
		st=1;
	dr=n;
	while(st<dr)
	{
	mid=(st+dr)/2;
	if(a[mid]<val)st=mid+1;
	else dr=mid;
	}
	mid=(st+dr)/2;
	if(a[mid]<val)++mid;
	return mid;
}

main(void)
{
	cin>>n;
	for(i=1;i<=n;++i)cin>>a[i];
	cin>>m;
	for(i=1;i<=m;++i){
		cin>>q>>nr;
		if(!q)cout<<cautbin1(nr)<<'\n';
		else if(q==1)cout<<cautbin2(nr)<<'\n';
		else if(q==2)cout<<cautbin3(nr)<<'\n';
	}
}