#include<fstream>

using namespace std;

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

int v[100001],n,m;

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

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

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

int main()
{
	int i,ef,x;
	in>>n;
	for(i=1;i<=n;i++)
		in>>v[i];
	in>>m;
	for(i=1;i<=m;i++)
	{
		in>>ef>>x;
		if(ef==0)
			out<<cautbin0(x)<<"\n";
		else if(ef==1)
			out<<cautbin1(x)<<"\n";
		else out<<cautbin2(x)<<"\n";
	}
	in.close();
	out.close();
	return 0;
}