#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, s;
	f >> n;
	for (int i = 1; i <= n; i++) {
		f >> a;
		v.push_back(a);
	}
    s=v.size();
	f >> c;
	for (int i = 1; i <= c; i++) {
		f >> a >> x;
		if (a == 0) {
			p = upper_bound(v.begin(), v.end(), x) - v.begin();
			if (p < s) g << p << endl;
			else g << -1 << "\n";
		}
		else if (a == 1) {
			p = lower_bound(v.begin(), v.end(), x + 1) - v.begin();
			g << p << "\n";
		}
		else {
			p = upper_bound(v.begin(), v.end(), x - 1) - v.begin() + 1;
			g << p << "\n";
		}
	}

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