#include <fstream>

using namespace std;

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

int main() {
	int n, m, s[100001], i, j, tip, x;

	//citim lungimea sirului si sirul
	fin >> n;
	for (i = 1; i <= n; ++i) 
		fin >> s[i];

	//citim nr intrebari, intrebarile si raspundem la fiecare
	fin >> m;
	for (i = 0; i < m; ++i) {
		fin >> tip >> x;
		//1. cautare pe x in s
		int lt = 1, rt = n, mid;
		while (lt <= rt) {
			mid = (lt + rt) / 2;
			if (s[mid] < x) 
				lt = mid + 1;
			else if (s[mid] > x)
				rt = mid - 1;
			else 
				break;
			//asa e facut sa dea cautarea binara, lt cea mai mica poz a elem >= x si rt cea mai mare poz a elem <= x, daca x nu E
		}
		//afisare in functie de E lui x si tip intrebare
		if (s[mid] == x) { 
			if (tip < 2) { 
				while (mid <= n && s[mid] == x) ++mid;
				--mid; //e ultima poz a lui x
			}
			else { 
				while (mid > 0 && s[mid] == x) --mid;
				++mid; //prima poz a lui x
			}
			fout << mid;
		}
		else {
			if (tip == 0) fout << -1;
			else if (tip == 1) fout << rt;
			else fout << lt;
		}
		fout << "\n";
	}
}