#include<fstream>
using namespace std;

#define kozep (kp + vp) / 2

int bs0(int kp, int vp, unsigned int sir[], unsigned int nr) {
	while (true)
	{
		if (kp == vp && sir[vp] != nr) return -2;
		if (nr == sir[kozep])
			if (nr != sir[kozep + 1]) return kozep;
			else kp = kozep + 1;
		else 
			if (nr < sir[kozep]) vp = kozep - 1;
			else kp = kozep + 1;
	}
}

int bs1(int kp, int vp, unsigned int sir[], unsigned int nr) {
	while (true)
	{
		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 kp = kozep + 1;
		else
			if (nr < sir[kozep]) vp = kozep - 1;
			else kp = kozep + 1;
	}
}

int bs2(int kp, int vp, unsigned int sir[], unsigned int nr) {
	while (true)
	{
		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]) vp = kozep - 1;
			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;
		switch (command)
		{
		case 0: out << bs0(kp, vp, sir, nr) + 1 << "\n"; break;
		case 1: out << bs1(kp, vp, sir, nr) + 1 << "\n"; break;
		case 2: out << bs2(kp, vp, sir, nr) + 1 << "\n"; break;
		default:
			break;
		}
	}
}