#include<fstream>
using namespace std;
int n,m;
int v[100001];
int caut_binar0(int x)
{
	int st=0,dr=n,mij,poz;
	while(st<=dr)
	{
		mij=st+(dr-st)/2;
		if(v[mij]==x)
			poz=mij;
		if(v[mij]>x)
			dr=mij-1;
		if(v[mij]<=x)
			st=mij+1;
	}
	return poz;
}
int caut_binar1(int x)
{
	int st=0,dr=n,mij,poz;
	while(st<=dr)
	{
		mij=st+(dr-st)/2;
		if(v[mij]<=x)
			poz=mij;
		if(v[mij]>x)
			dr=mij-1;
		if(v[mij]<=x)
			st=mij+1;
	}
	return poz;
}
int caut_binar2(int x)
{
	int st=0,dr=n,mij,poz;
	while(st<=dr)
	{
		mij=st+(dr-st)/2;
		if(v[mij]>=x)
			poz=mij;
		if(v[mij]>=x)
			dr=mij-1;
		if(v[mij]<x)
			st=mij+1;
	}
	return poz;
}
int main()
{
	ifstream fin("cautbin.in");
	ofstream fout("cautbin.out");
	fin>>n;
	for(int i=1;i<=n;++i)
		fin>>v[i];
	fin>>m;
	for(;m;--m)
	{
		int tip,x;
		fin>>tip>>x;
		if(tip==0 && v[n]<x)
			fout<<"-1\n";
		else
			if(tip==0)
				fout<<caut_binar0(x)<<"\n";
		if(tip==1)
			fout<<caut_binar1(x)<<"\n";
		if(tip==2)
			fout<<caut_binar2(x)<<"\n";
	}
}