#include <fstream>

using namespace std;

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

int v[100001];

int i,s,m, n, x;

int cautbin0() {
	s=n;
	i=1;
	while (i<=s) {
		m=(i+s)/2;
		if(v[m]<=x)
			i=m+1;
		else
			s=m-1;
	}
	if(v[s]==x)
		return s;
	else
		return -1;
}
int cautbin1() {
	s=n;
	i=1;
	while (i<=s) {
		m=(i+s)/2;
		if(v[m]<=x)
			i=m+1;
		else
			s=m-1;
	}
	return s;
}
int cautbin2() {
	s=n;
	i=1;
	while (i<=s) {
		m=(i+s)/2;
		if(v[m]<=x)
			i=m+1;
		else
			s=m-1;
	}
	return i;
}
int main() {
	int m, intr,i;
	fin >> n;
	for (i = 1; i <= n; i++)
		fin >> v[i];
	fin >> m;
	for (i = 1; i <= m; i++) {
		fin >> intr >> x;
		if (intr == 0)
			fout << cautbin0() << '\n';
		if (intr == 1)
			fout << cautbin1() << '\n';
		if (intr == 2)
			fout << cautbin2() << '\n';
	}
	return 0;
}