#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

std::ifstream in("cautbin.in");
std::ofstream out("cautbin.out");

int CautaBinar(std::vector<int> &vec, int &elem, int low, int high)
{
	unsigned int mid;
	while(low <= high)
	{
		mid = low + (high - low) / 2;
		if(vec[mid] <= elem)
		{
			low = mid + 1;
		}
		else
		{
			high = mid - 1;
		}
	}
	mid = (low + high) / 2;
	if(vec[mid] > elem)
	{
		mid--;
	}
	if(vec[mid] == elem)
	{
		return mid;
	}
	return -1; // nu s a gasit element
}

int CautaBinar1(std::vector<int> &vec, int &elem, int low, int high)
{
	int mid = low + (high - low) / 2;
	while(high > low)
	{
		mid = low + (high - low) / 2;
		if(vec[mid] > elem)
		{
			high = mid;
		} 
		else
		{
			low = mid + 1;
		}
	}
	mid = (low + high) / 2;
	if(vec[mid] > elem)
	{
		mid--;
	} 
	return mid;
}

int CautaBinar2(std::vector<int> &vec, int &elem, int low, int high)
{
	int mid = low + (high - low) / 2;
	while(low <= high)
	{
		mid = low + (high - low) / 2;
		if(vec[mid] >= elem)
		{
			high = mid - 1;
		} 
		else
		{
			low = mid + 1;
		}
	}
	mid = (low + high) / 2;
	if(vec[mid] < elem)
	{
		mid++;
	}
	return mid;
}

void getRequests(std::vector<int> &vec, std::pair<int , int> &p, int &dimVec)
{
	int poz;
	if(p.first == 0)
	{
		poz = CautaBinar(vec, p.second, 0, dimVec - 1);
		// in output vectorul este contorizat de la 1 la n
		out << poz << "\n";
	}
	else if(p.first == 1)
	{
		poz = CautaBinar1(vec, p.second, 0, dimVec - 1);
		out << poz << "\n";
	}
	else
	{
		//std::cout << p.first << "\n";
		poz = CautaBinar2(vec, p.second, 0, dimVec - 1);
		out << poz << "\n";
	}
} 

int main(void)
{
	int dimVec;
	in >> dimVec;

	std::vector<int> vec;
	int elem;
	for(int i = 0; i < dimVec; i++)
	{
		in >> elem;
		vec.push_back(elem);
	}

	int requests;
	in >> requests;

	// first -> tipul cererii
	// second -> numarul pe cerere
	std::vector < std::pair <int, int> > v;
	int type;
	int number;

	for(int i = 0; i < requests; i++)
	{
		in >> type;
		in >> number;
		std::pair <int, int> p(type, number);
		v.push_back(p);
	}

	for(int i = 0; i < requests; i++)
	{
		getRequests(vec, v[i], dimVec);
	}
}