#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";
	}
}