#include<iostream>
#include<fstream>
#include<vector>
using namespace std;

int N, m, k;
vector<int> V;

ofstream g("cautbin.out", ios::out);

void bin0(int val){
	int start = 1;
	int end = V.size()-1;

	while (start <= end){
		m = (start + end) / 2;
		if (V[m] <= val) start = m+1;
		else end = m - 1;
	}

	m = (start + end) / 2;

	if (V[m] > val) m--;
	if (V[m] == val) g<< m << '\n';
	else g << "-1\n";


}

void bin1(int val){
	int start = 1;
	int end = V.size() - 1;

	while (start < end){
		m = (start + end) / 2;
		if (V[m] <= val) start = m + 1;
		else end = m;

	}

	m = (start + end) / 2;

	if (V[m] > val) m--;
	g << m << '\n';

}

void bin2(int val){
	int start = 1;
	int end = V.size();

	while (start < end){
		m = (start + end) / 2;
		if (V[m] < val) start = m + 1;
		else end = m ;

	}
	m = (start + end) / 2;

	if (V[m] < val) m++;
	g << m << '\n';




}

int main(){
	ifstream f("cautbin.in", ios::in);


	f >> N;
	V.push_back(0);
	for (int i = 0; i < N; i++){
		f >> k;
		V.push_back(k);
	}
	f >> m;

	int com, val;
	for (int i = 0; i < m; i++){
		f >> com >> val;
		if (com == 0) bin0(val);
		else if (com == 1) bin1(val);
		else bin2(val);
	}

	f.close();
	g.close();
	return 0;
}