#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

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

int main()
{
	vector <int> v;
	int n, c, a, x, p;

	f >> n;
	for (int i = 1; i <= n; i++) {
		f >> a;
		v.push_back(a);
	}

	f >> c;
	for (int i = 1; i <= c; i++) {
		f >> a >> x;
		if (a == 0) {
			if (binary_search(v.begin(), v.end(), x)){
				g << (upper_bound(v.begin(), v.end(), x) - v.begin()) << "\n";
			}
			else g << -1 << "\n";
		}
		else if (a == 1) {
			if (binary_search(v.begin(), v.end(), x))
				g << (upper_bound(v.begin(), v.end(), x) - v.begin()) << "\n";
			else g << (lower_bound(v.begin(), v.end(), x) - v.begin()) << "\n";
		}
		else {
			if (binary_search(v.begin(), v.end(), x))
				g << (lower_bound(v.begin(), v.end(), x) - v.begin()) + 1 << "\n";
			else g << (upper_bound(v.begin(), v.end(), x) - v.begin()) + 1 << "\n";
		}
	}

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