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

#include <fstream>
#include <algorithm>
#include <iomanip>
#define N 100000
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int v[N], n;
void citire() {
	fin >> n;
	for (int i = 0; i < n; i++)fin >> v[i];
}
int cb1(int s, int d, int x) {
	int m;
	if (x == v[n - 1])return n - 1;
	while (s <= d) {
		m = (s + d) / 2;
		//fout << s << " " << d << " " << m << "\n";
		if (v[m] == x && v[m + 1] > x)return m;
		if (v[m] <= x)s = m + 1;
		else d = m - 1;
	}
	return -2;
}
int cb2(int s, int d, int x) {
	int m;
	if (x >= v[n - 1])return n - 1;
	while (s <= d) {
		m = (s + d) / 2;
		//fout << s << " " << d << " " << m << "\n";
		if (v[m] <= x && v[m + 1] > x)return m;
		if (v[m] <= x)s = m + 1;
		else d = m - 1;
	}
	return -2;
}
int cb3(int s, int d, int x) {
	int m;
	if (x <= v[0])return 0;
	while (s <= d) {
		m = (s + d) / 2+(s+d)%2;
		//fout << s << " " << d << " " << m << " " << v[m] << " " << v[m - 1] << "\n";
		if (v[m] >= x && v[m - 1] < x)return m;
		if (v[m] > x)s = m + 1;
		else d = m - 1;
	}
	return -2;
}
void rez() {
	int m, i, op, x;
	fin >> m;
	for (i = 0; i < m; i++) {
		fin >> op >> x;
		if (op == 0)fout << cb1(0, n - 1, x) + 1 << "\n";
		else if (op == 1)fout << cb2(0, n - 1, x) + 1 << "\n";
		else fout << cb3(0, n - 1, x) + 1 << "\n";
	}
}
int main() {
	citire();
	//fout << cb3(0, n - 1, 3) + 1;
	rez();
	return 0;
}
// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file