#include<fstream>
using namespace std;

#define kozep (kp + vp) / 2

int bs(int kp, int vp, unsigned int sir[], unsigned int nr, short command) {
	while (true)
	{
		if (kp == vp)
			switch (command)
			{
			case 0: if (sir[vp] != nr) return -2; break;
			case 1: if (sir[kp]>nr) return kp - 1;
					else return kp; break;
			case 2: if (sir[kp]<nr) return kp + 1;
					else return kp; break;
			default:
				break;
			}
		if (kp == vp)
			if (sir[kp]<nr) return kp + 1;
			else return kp;
		if (nr == sir[kozep])
			if (nr != sir[kozep - 1]) return kozep;
			else vp = kozep - 1;
		else
			if (nr < sir[kozep])
				if (kozep != kp)vp = kozep - 1;
				else vp--;
			else kp = kozep + 1;
	}
}

int main() {
	ifstream in("cautbin.in");
	ofstream out("cautbin.out");
	int N;	in >> N;
	unsigned int sir[100000];
	for (int i = 0; i < N; ++i)
		in >> sir[i];
	int M;	in >> M;
	
	for (;M;--M) {
		short command;		in >> command;
		unsigned int nr;	in >> nr;
		int kp = 0, vp = N - 1;
		out << bs(kp, vp, sir, nr, command) + 1 << "\n";
	}
}