// FMI - Grupa 135 - Semigrupa 2 - Hareza Andrei
// Include
#include <fstream>
using namespace std;

// Constante
const int sz = 100001;

// Functii
template<class T> int binarySearch(T *data, int left, int right, T value, bool (*comp)(T a, T b));
bool lowerEqual(int a, int b) { return a<=b; }
bool lower(int a, int b) { return a<b; }

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

int num, questions;
int values[sz];

int type, value;

// Main
int main()
{
	in >> num;
	for(int i=1 ; i<=num ; ++i)
		in >> values[i];
	
	in >> questions;
	
	while(questions--)
	{
		in >> type >> value;
		switch(type)
		{
		case 0:
			{
				int pos = binarySearch(values, 1, num, value, lower)-1;
				out << (values[pos] == value? pos : -1) << '\n';
				break;
			}
		case 1:
			{
				out << binarySearch(values, 1, num, value, lower)-1 << '\n';
				break;
			}
		case 2:
			{
				out << binarySearch(values, 1, num, value, lowerEqual) << '\n';
				break;
			}
			
		}
		
	}
	
	in.close();
	out.close();
	return 0;
}

template<class T> int binarySearch(T *data, int left, int right, T value, bool (*comp)(T a, T b))
{
	if(comp(value, data[left]))
		return left;
	
	if(!comp(value, data[right]))
		return right+1;
	
	int dif = right - left + 1;
	data += left;
	right -= left;
	int pos = 0;
	int power = 0;
	
	while(1<<++power <= dif);
	
	while(power--)
	{
		if(right <= pos + (1<<power))
			continue;
		
		if(!comp(value, data[pos+(1<<power)]))
			pos += 1<<power;
	}
	
	return pos+left+1;
}