#include <fstream>
#define MAXN 100004
using namespace std;

int n, x[MAXN], m;

int bin_Search0(int z)
{
	int st = 1, dr = n, mid;
	
	while(st <= dr)
	{
		mid = (st + dr) / 2;
		
		if(x[mid] <= z)
			st = mid + 1;
	
		if(x[mid] > z)
			dr = mid - 1;
	}
	
	mid = (st + dr) / 2;
	
	if(x[mid] > z)
		--mid;
	
	if(x[mid] == z)
		return mid;
	
	return -1;	
}

int bin_Search1(int z)
{
	int st = 1, dr = n, mid;
	
	while(st < dr)
	{
		mid = (st + dr) / 2;
		
		if(x[mid] > z)
			dr = mid;
		
		if(x[mid] <= z)
			st = mid + 1;
		
	}

	mid = (st + dr) / 2;
	
	if(x[mid] > z)
		--mid;
	
	return mid;
}


int bin_Search2(int z)
{
	int st = 1, dr = n, mid;
	
	while(st < dr)
	{
		mid = (st + dr) / 2;
		
		if(x[mid] < z)
			st = mid + 1;
		
		if(x[mid] >= z)
			dr = mid;
	}
	
	mid = (st + dr) / 2;

	if(x[mid] < z)
		++mid;
	
	return mid;
	
}


int main()
{
	ifstream f("cautbin.in");
	ofstream g("cautbin.out");
	
	f >> n;
	
	for(int i = 1; i <= n; ++i)
		f >> x[i];
	
	for(f >> m; m; --m)
	{
		int tip, z;
		
		f >> tip >> z;
		
		if(!tip)
			g << bin_Search0(z) << '\n';
		if(tip == 1)
			g << bin_Search1(z) << '\n';
		if(tip == 2)
			g << bin_Search2(z) << '\n';
		
	}
	
}