#include <iostream>
#include <fstream>
using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int v[100001];
void caut_bin(int a, int b, int x, int nr) {
	int st = a, dr = b, rez = -1;
	while (st <= dr) {
		int m = (st + dr) / 2;
		if (nr == 0) {
			if (v[m] < x) st = m + 1;
			else if (v[m] == x) {
				rez = m;
				st = m + 1;
			}
			else dr = m - 1;
		}
		else if (nr == 1) {
			if (v[m] > x) dr = m - 1;
			else if (v[m] <= x) {
				rez = m;
				st = m + 1;
			}
		}
		else if (nr == 2) {
			if (v[m] < x) st = m + 1;
			if (v[m] >= x) {
				rez = m;
				dr = m - 1;
			}
		}
	}
	out << rez << '\n';
}

int main() {
	int n, m, nr, y;
	in >> n;
	for (int i = 1; i <= n; i++) in >> v[i];
	in >> m;
	for (int i = 1; i <= m; i++) {
		in >> nr >> y;
		caut_bin(1, n, y, nr);
	}
}