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

//#include "pch.h"
#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) {
		if (v[min] != val) return -1;
		else return min;
	}
	int mij = (max + min) / 2;
	if (v[mij] > val) return search0(min, mij, val); // Cautare in intercalul minim - mijloc
	else if (v[mij] < val) return search0(mij, max, val); // Cautare in intervalul mijloc - maxim
}

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

/* Cautarea unei valori <= in sir */
int search2(int min, int max, int val) {
	if (min > max) return max;
	if (min == max || max-min==1) return min;
	int mij = (max + min) / 2;
	if (v[mij] >= val) return search1(min, mij, val); // Cautare in intercalul minim - mijloc
	else if (v[mij] < val) return search1(mij, 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;
}