// cautbin.cpp : Defines the entry point for the console application.
//

#include <iostream>
#include <fstream>
#define MAXN 10005
#define MAX(a,b) ( (a) > (b) ? (a) : (b))

using namespace std;

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

int N, M, v[MAXN];

void cit() {
	in >> N;
	for (int i = 1; i <= N; i++) {
		in >> v[i];
	}

}
int cautbin_0(int nr) {
	int mid, st = 1, dr = N;
	while (st <= dr) {

		mid = (st + dr) / 2;
		if (v[mid] > nr) {
			dr = mid - 1;
		}
		else if (v[mid] <= nr) {
			st = mid + 1;
		}
	}
	mid = (st + dr) / 2;
	if (v[dr] == nr) {
		return dr;
	}
	else {
		return -1;
	}
}
int cautbin_1(int nr) {
	int mid, st = 1, dr = N;
	while (st <= dr) {

		mid = (st + dr) / 2;
		if (v[mid] > nr) {
			dr = mid - 1;
		}
		else if (v[mid] <= nr) {
			st = mid  + 1;
		}
	}
	mid = (st + dr) / 2;
	return dr;
	
}
int cautbin_2(int nr) {
	int mid, st = 1, dr = N;
	while (st <= dr) {

		mid = (st + dr) / 2;
		if (v[mid] >= nr) {
			dr = mid - 1;
		}
		else if (v[mid] < nr) {
			st = mid + 1;
		}
	}
	mid = (st + dr) / 2;
	return st;
}

int main()
{
	cit();
	in >> M;
	for (int i = 1; i <= M; i++) {
		int a, nr;
		in >> a >> nr;
		if (a == 0) {
			out << cautbin_0(nr) << "\n";
		}
		else if (a == 1) {
			out << cautbin_1(nr) << "\n";
		}
		else {
			out << cautbin_2(nr) << "\n";
		}
	}
	return 0;
}