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

int main(){
	ifstream f("cautbin.in");
	ofstream g("cautbin.out");
	int n = 0;
	f >> n;
	vector<int> v(n);
	for(auto& x : v){
		f >> x; }
	int m = 0;
	f >> m;
	for(int i = 0, a, b; i < m; ++i){
		f >> a >> b;
		if(a == 0){
			if(binary_search(begin(v), end(v), b)){
				g << (upper_bound(begin(v), end(v), b) - begin(v)) << '\n'; }
			else{
				g << "-1\n"; } }
		else if(a == 1){
			g << (upper_bound(begin(v), end(v), b) - begin(v)) << '\n'; }
		else{
			g << (lower_bound(begin(v), end(v), b) - begin(v) + 1) << '\n'; } }
	return 0; }