#include <iostream>
#include <fstream>

using namespace std;

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

const int NMAX = 100000;

int n;
int v[NMAX + 1];

void citeste() {
	f >> n;
	for (int i = 1; i <= n; i++) f >> v[i];
}

// cea mai mare pozitie pe care se afla un element cu valoarea x 
// sau -1 daca aceasta valoare nu se gaseste in sir
int caut0(int x) {
	int sol = -1;
	int st = 1, dr = n;

	while (st <= dr) {
		int m = (st + dr) / 2;
		if (v[m] == x) {
			sol = m;
		}
		if (v[m] >= x) st = m + 1;
		else dr = m - 1;
	}

	return sol;
}

// cea mai mare pozitie pe care se afla un element cu valoarea
// mai mica sau egala cu x in sir
int caut1(int x) {
	int sol = -1;
	int st = 1, dr = n;

	while (st <= dr) {
		int m = (st + dr) / 2;
		if (v[m] <= x) {
			sol = m;
			st = m + 1;
		}
		else dr = m - 1;
	}

	return sol;
}

// cea mai mica pozitie pe care se afla un element cu valoarea 
// mai mare sau egala cu x in sir
int caut2(int x) {
	int sol = -1;
	int st = 1, dr = n;

	while (st <= dr) {
		int m = (st + dr) / 2;
		if (v[m] >= x) {
			sol = m;
			dr = m - 1;
		}
		else st = m + 1;
	}

	return sol;
}

int caut(int op, int x) {
	if (op == 0) return caut0(x);
	if (op == 1) return caut1(x);
	return caut2(x);
}


int main() {
	citeste();
	int m, op, x;
	f >> m;
	for (int i = 1; i <= m; i++) {
		f >> op >> x;
		g << caut(op, x) << '\n';
	}
	return 0;
}