#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>


int caut_bin(int x, std::vector<int> & v,int st,int dr);

int caut_bin2(int x, std::vector<int> & v,int st,int dr);

int main(){

	std::ifstream in("cautbin.in");
	std::ofstream out("cautbin.out");
	std::vector<int> v;

	int N, M, x, op,nr,rez;

	in >> N;

	for(int  i = 0; i < N; i++){
		in >> x;
		v.push_back(x);
	}
	std::sort(v.begin(), v.end());

	in >> M;

	for(int i = 0; i < M; i++){
		in >> op >> nr;

		if(op == 0){
			rez = caut_bin(nr, v, 0, v.size() - 1) - 1;
			if( v[rez] == nr)
				out << rez + 1 << "\n";
			else
				out << -1 <<"\n";
		}

		if (op == 1)
			out << caut_bin(nr, v, 0, v.size() - 1)<<"\n";

		if(op == 2)
			out << caut_bin2(nr, v, 0, v.size() - 1) + 1<<"\n";
	}

	in.close();
	out.close();
	return 0;

}


int caut_bin(int x, std::vector<int> & v,int st, int dr){

	//std::cout<<st<<" "<<dr<<"\n";
	if(st > dr)
		return st;

	int mij = st + (dr - st) / 2;
	

	if(v[mij] <= x)
		return caut_bin(x, v, mij + 1, dr);

	return caut_bin(x, v, st, mij - 1);
	//return -1;
}


int caut_bin2(int x, std::vector<int> & v,int st,int dr){

	if(st > dr)
		return st;

	int mij = st + (dr - st) / 2;

	if(v[mij] < x)
		return caut_bin2(x, v, mij+1, dr);

	return caut_bin2(x, v, st, mij - 1);
}