#include <fstream>
#include <algorithm>
using namespace std;

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

int sir[100100];
int N, M;

int main(int argc, char const *argv[])
{
	fin >> N;
	for (int i = 0; i < N; ++i) {
		fin >> sir[i];
	}
	fin >> M;
	for (int i = 0; i < M; ++i) {
		int c, x, pos;
		fin >> c >> x;
		if (c == 0) {
			pos = upper_bound(sir, sir+N, x) - sir - 1;
			if (pos >= N || pos < 0 || sir[pos] != x) {
				fout << -1;
			} else {
				fout << pos + 1;
			}
			fout << '\n';
		} else if (c == 1) {
			pos = lower_bound(sir, sir+N, x) - sir - 1;
			fout << pos + 1 << '\n';
		} else if (c == 2) {
			pos = upper_bound(sir, sir+N, x) - sir - 1;
			fout << pos + 1 << '\n';
		} else {
			fout << "ERROR" << endl;
		}
	}
	return 0;
}