#include <fstream>
using namespace std;
ifstream cin("cautbin.in");
ofstream cout("cautbin.out");
int v[100001],n;

int caut0(int x)
{
	int st=1,dr=n,mid;
	while(st!=dr)
	{
		mid=(st+dr+1)/2;
		if(x>=v[mid])
			st=mid;
		else
			dr=mid-1;
	}
	if(x==v[st])
		return st;
	return -1;
}
int caut1(int x)
{
	int st=1,dr=n,mid;
	while(st!=dr)
	{
		mid=(st+dr+1)/2;
		if(x>=v[mid])
			st=mid;
		else
			dr=mid-1;
	}
	if(v[st]>x)
		return st-1;
	return st;
}

int caut2(int x)
{
	int st=1,dr=n,mid;
	while(st!=dr)
	{
		mid=(dr-st)/2+st;
		if(x<=v[mid])
			dr=mid;
		else
			st=mid+1;
	}
	return st;
}
int main()
{
	int i,m,q,x;
	cin>>n;
	for(i=1;i<=n;i++)
		cin>>v[i];
	cin>>m;
	for(i=1;i<=m;i++)
	{
		cin>>q;
		cin>>x;
		if(q==0)
			cout<<caut0(x)<<"\n";
		if(q==1)
			cout<<caut1(x)<<"\n";
		if(q==2)
			cout<<caut2(x)<<"\n";
	
	}
	return 0;
}