#include <iostream>
#include <fstream>
using namespace std;

long long n , m;
int x [100005];

int job1 (int a)
{
	int st = 1 , dr = n , mij;
	while (st < dr - 1)
	{
		mij = (st + dr) / 2;
		if (x[mij] < a)
			st = mij + 1;
		else if (x[mij] == a)
			st = mij;
		else dr = mij - 1;
	}
	
	if (x[st] == a)
		return st;
	else if (x[dr] == a)
		return dr;
	return -1;
}
int job2 (int a)
{
	int st = 1 , dr = n , mij;
	while (st < dr - 1)
	{
		mij = (st + dr) / 2;
		if (x[mij] <= a)
			st = mij;
		else dr = mij - 1;
	}
	
	if (x[dr] <= a)
		return dr;
	return st;
}
int job3 (int a)
{
	int st = 1 , dr = n , mij;
	while (st < dr)
	{
		mij = (st + dr) / 2;
		if (x[mij] < a)
			st = mij + 1;
		else 
			dr = mij;
		}
	
	return st;
}
int main ()
{
	ifstream f ("cautbin.in");
	ofstream g ("cautbin.out");
	
	int nr , job;
	
	f >> n;
	for (int i = 1 ; i <= n ; ++i)
		f >> x[i];
	
	f >> m;
	for (int i = 1 ; i <= m ; ++i)
	{
		f >> job >> nr;
		if (job == 0)
			g << job1 (nr) << "\n";
		else if (job == 1)
			g << job2 (nr) << "\n";
		else 
			g << job3 (nr) << "\n";
	}
	
	return 0;
}