#include <fstream>
using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int n, *v;

int cautbin(int val) {
    int low = 0, mid, high = n - 1;

    while (v[low] != v[high]) {
		mid = (low + high + 1) >> 1;
		if (v[mid] <= val)
			low = mid;
		else
			high = mid - 1;
	}

	return high;
}
int main()
{
    fin >> n;
	v = new int[n];
	for (int i = 0; i < n; ++i)
		fin >> v[i];

	int m, t, val, rez;
	for (fin >> m; m > 0; --m) {
		fin >> t >> val;
		switch (t) {
		case 0:
			rez = cautbin(val);
			if (v[rez] != val) {
				rez = -2;
			}
			break;
		case 1:
			rez = cautbin(val);
			break;
		case 2:
			rez = cautbin(val - 1);
			if (v[rez] < val) {
				++rez;
			}
			break;
		}
		fout << ++rez << "\n";
	}
}