#include <iostream>
#include <fstream>
#define mod 666013
using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");


int main()
{
	int n, m, a[100005];
	in >> n;
	for (int i = 1; i <= n; i++) {
		in >> a[i];
	}
	in >> m;
	for (int i = 1; i <= m; i++) {
		int x, y;
		in >> x >> y;
		int elem = y;
		if (x < 2) {
			elem += 1;
		}
		int l = 1, r = n;
		while (l!=r) {
			int mij = (r + l) / 2;
			if (a[mij] < elem) {
				l = mij + 1;
			}
			else {
				r = mij;
			}
		}
		if (x == 0) {
			if (a[l] == y) {
				out << l;
				goto fin;
			}
			if (l > 1 && a[l - 1] == y) {
				out << l - 1;
				goto fin;
			}
			out << -1;
		}
		if (x == 1) {
			if (a[l] <= y) {
				out << l;
				goto fin;
			}
			out << l - 1;
		}
		if (x == 2) {
			out << l;
		}
		fin:
		out << '\n';
	}
	return 0;
}