#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <vector>
using std::cout;

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

// https://www.infoarena.ro/problema/cautbin 
// https://www.infoarena.ro/multe-smenuri-de-programare-in-cc-si-nu-numai

const int Nmax = 100005;

int search0(int arr[], int left, int right, int nr)
{
	while(left < right)
	{
		int mid = (left + right) / 2;
		if(arr[mid] > nr)
			right = mid - 1;
		else
			left = mid + 1;
	}

	if(arr[left] == nr)
		return left;
	else if(left > 0 && arr[left - 1] == nr)
		return left - 1;
	else	
		return -1;
}

int search1(int arr[], int left, int right, int nr)
{
	while(left < right)
	{
		int mid = (left + right) / 2;
		if(arr[mid] > nr)
			right = mid - 1;
		else	
			left = mid + 1;
	}
	if(arr[left] == nr)
		return left;
	return left - 1;
}

int search2(int arr[], int left, int right, int nr)
{
	while(left < right)
	{
		int mid = (left + right) / 2;
		if(arr[mid] < nr)
			left = mid + 1;
		else
			right = mid - 1;		
	}
	if(arr[left] == nr)
		return left;
	return left + 1;	
}

int main()
{
	int n, m, c, x;
	int arr[Nmax];

	fin >> n;
	for(int i = 0; i < n; i++)
		fin >> arr[i];
	fin >> m;
	
	for(int i = 0; i < m; i++)
	{
		fin >> c >> x;

		if(c == 0)
			cout << search0(arr, 0, n, x) + 1<< ' ';
		else if(c == 1)
			cout << search1(arr, 0, n, x) + 1<< ' ';
		else
			cout << search2(arr, 0, n, x) + 1<< ' ';
	}
}