#include <iostream>
#include <fstream>


#include <vector>
using namespace std;

// Intoarce cea mai mare pozitie pe care se afla x sau -1.
int bsearch0(int v[], int x, int left, int right) {
	int m;

	while (left <= right) {
		m = left + (right - left) / 2;
		if (v[m] == x && v[m + 1] != x) return m;
		else if (v[m] > x) right = m - 1;
		else left = m + 1;
	}

	return -1;
}

// Intoarce cea mai mare pozitie pe care se afla un element
// cu valoarea mai mica sau egala cu x.
int bsearch1(int v[], int x, int left, int right) {
	int m;

	while (left < right) {
		m = left + (right - left) / 2;
		if (v[m] > x) right = m - 1;
		else left = m + 1;
	}

	if (v[left] > x) return left - 1;
	else return left;
}

// Intoarce cea mai mica pozitie pe care se afla un element
// cu valoarea mai mare sau egala cu x.
int bsearch2(int v[], int x, int left, int right) {
	int m;

	while (left < right) {
		m = left + (right - left) / 2;
		if (v[m] >= x) right = m - 1;
		else left = m + 1;
	}

	if (v[left] < x) return left + 1;
	else return left;
}

int v[100001];

int main()
{
	ifstream f("cautbin.in");
	ofstream g("cautbin.out");

	int n, x, op, nr_op;

	// Citeste vectorul.
	f >> n;
	for (int i = 1; i <= n; i++) {
		f >> v[i];
	}

	// Citeste si executa fiecare test.
	f >> nr_op;
	for (int i = 0; i < nr_op; i++) {
		f >> op >> x;
		if (op == 0) {
			g << bsearch0(v, x, 1, n) << endl;
		}
		else if (op == 1) {
			g << bsearch1(v, x, 1, n) << endl;
		}
		else if (op == 2) {
			g << bsearch2(v, x, 1, n) << endl;
		}
	}

	f.close();
	g.close();
    return 0;
}