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

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

int job1 (int a)
{
	int hi = n + 1 , lo = -1, mid;
	
    while (hi - lo > 1) 
	{
		mid = (lo + hi) / 2;
		
		if (x[mid] <= a)
			lo = mid;
		else
			hi = mid;
    }
	
    if (lo == n + 1 || x[lo] != a)
        return -1;
	
    else
        return lo;
}


int job2 (int a)
{
	int hi = n + 1 , lo = -1, mid;
	
    while (hi - lo > 1) 
	{
		mid = (lo + hi) / 2;
		
		if (x[mid] <= a)
			lo = mid;
		
		else
			hi = mid;
    }
	
	return lo;
}


int job3 (int a)
{
	int hi = n + 1 , lo = -1, mid;
	
    while (hi - lo > 1) 
	{
		mid = (lo + hi) / 2;
		
		if (x[mid] < a)
			lo = mid;
		
		else
			hi = mid;
    }
	
	return hi;
}


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;
}