// BinarySearch.cpp : This file contains the 'main' function. Program execution begins and ends there.
//


#include <iostream>
#include <fstream>

using namespace std;

class Intrebare {
public:
	int intrebare, cautat;
};

int *v;

/* Cautarea unei valori == in sir */
int search0(int min, int max, int val) {
	if (min > max) return -1;
	if (min == max && v[min] != val) return -1;
	int mij = (max + min) / 2;
	if (v[mij] == val) return mij; // A fost gasita pozitia cautata
	else if (v[mij] > val) return search0(min, mij - 1, val); // Cautare in intercalul minim - mijloc
	else if (v[mij] < val) return search0(mij + 1, max, val); // Cautare in intervalul mijloc - maxim
}

/* Cautarea unei valori >= in sir */
int search1(int min, int max, int val) {
	if (min > max) return -1;
	int mij = (max + min) / 2;
	if (v[mij] >= val && min-max<=1) return mij; // A fost gasita pozitia cautata
	else if (v[mij] > val) return search1(min, mij - 1, val); // Cautare in intercalul minim - mijloc
	else if (v[mij] < val) return search1(mij + 1, max, val); // Cautare in intervalul mijloc - maxim
}

/* Cautarea unei valori <= in sir */
int search2(int min, int max, int val) {
	if (min > max) return -1;
	int mij = (max + min) / 2;
	if (v[mij] <= val && min - max <= 1) return mij; // A fost gasita pozitia cautata
	else if (v[mij] > val) return search1(min, mij - 1, val); // Cautare in intercalul minim - mijloc
	else if (v[mij] < val) return search1(mij + 1, max, val); // Cautare in intervalul mijloc - maxim
}
Intrebare *qst;

int main() {
	int length, questions;
	ifstream in("cautbin.in");
	ofstream out("cautbin.out");

	in >> length;
	v = new int[length];
	for (int i = 0; i < length; i++) {
		in >> v[i];
	}

	in >> questions;

	qst = new Intrebare[questions];

	for (int i = 0; i < questions; i++) {
		in >> qst[i].intrebare >> qst[i].cautat;
	}

	for (int i = 0; i < questions; i++) {
		switch (qst[i].intrebare)
		{
		case 0:
			out << search1(0, length, qst[i].cautat) << "\n";
			break;
		case 1:
			out << search1(0, length, qst[i].cautat) << "\n";
			break;
		case 2:
			out << search2(0, length, qst[i].cautat) << "\n";
		default:
			break;
		}
	}
	return 0;
}