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

// Constante
const int sz = 100003;

// Functii
template<class T> int binarySearch(T *data, int left, int right, T value, bool (*comp)(T a, T b));
template<class T> int binarySearchA(T *data, int left, int right, T value, bool (*comp)(T a, T b));
template<class T> bool lowerEqual(T a, T b);
template<class T> bool lower(T a, T 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))
{
	int lft = data[left-1];
	int rgh = data[right+1];
	
	data[left-1] = INT_MIN;
	data[right+1] = INT_MAX;
	
	return binarySearchA(data, left-1, right+1, value, comp);
	
	data[left-1] = lft;
	data[right+1] = rgh;
}

template<class T> int binarySearchA(T *data, int left, int right, T value, bool (*comp)(T a, T b))
{
	if(left == right)
		return left;
	
	int mid = (left+right)/2;
	
	if(comp(value, data[mid]))
		return binarySearchA(data, left, mid, value, comp);
	else
		return binarySearchA(data, mid+1, right, value, comp);
}

template<class T> bool lowerEqual(T a, T b)
{
	return a<=b;
}

template<class T> bool lower(T a, T b)
{
	return a<b;
}