#include<fstream>

using namespace std;

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

int v[100001],n;

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

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

int caut2(int x)
{
	int st=1, dr=n,mijl;
	while(st!=dr)
	{
		mijl=(st+dr)/2;
		if(x<=v[mijl])
			dr=mijl;
		else
			st=mijl+1;
	}
	if(v[st]<x)
		return st+1;
	return st;
}

int main()
{
	int i,j,m,x;
	in>>n;
	for(i=1;i<=n;++i)
		in>>v[i];
	in>>m;
	for(i=1;i<=m;++i)
	{
		in>>j;
		in>>x;
		if(j==0)
			out<<caut0(x)<<"\n";
		if(j==1)
			out<<caut1(x)<<"\n";
		if(j==2)
			out<<caut2(x)<<"\n";
	}
}