#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

#ifdef LOCAL
ifstream f("input.txt");
#define g cout
#else
ifstream f("cautbin.in");
ofstream g("cautbin.out");
#endif

const int mxN = 1e5 + 5;

int n, m, a[mxN];
int x, tip;

int cb1(int x) {
	int st = 1, dr = n, mij;
	while (st <= dr) {
		mij = (st + dr) / 2;
		if (a[mij] > x)
			dr = mij - 1;
		else
			st = mij + 1;
	}
	if (a[dr] != x)
		return -1;
	return dr;
}

int cb2(int x) {
	int st = 1, dr = n, mij;
	while (st <= dr) {
		mij = (st + dr) / 2;
		if (a[mij] > x)
			dr = mij - 1;
		else
			st = mij + 1;
	}
	return dr;
}

int cb3(int x) {
	int st = 1, dr = n, mij;
	while (st <= dr) {
		mij = (st + dr) / 2;
		if (a[mij] < x)
			dr = mij - 1;
		else
			st = mij + 1;
	}
	return dr;
}

int main() {
	f >> n;
	for (int i = 1; i <= n; i++)
		f >> a[i];
	
	f >> m;
	for (int i = 1; i <= m; i++) {
		f >> tip >> x;
		if (tip == 0)
			g << cb1(x);
		else if (tip == 1)
			g << cb2(x);
		else
			g << cb3(x);
		g << '\n';
	}
	
	return 0;
}