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

using namespace std;

int binarySearch(vector<int> &vect, int target) {
	int lo = 0, hi = vect.size() , mi;

	while (lo <= hi) {
		mi = lo + (hi - lo) / 2;
		if (vect[mi] == target) {
			while (vect[mi + 1] == target) ++mi;
			return mi + 1;
		} else if (vect[mi] > target) {
			hi = mi - 1;
			mi = lo + (hi - lo) / 2;
		} else {
			lo = mi + 1;
			mi = lo + (hi - lo) / 2;
		}
	}

	return -1;
}


int binarySearch1 (vector<int> &vect, int target) {
	int lo = 0, hi = vect.size(), mi;

	while (lo <= hi) {
		mi = lo + (hi - lo) / 2;
		if (vect[mi] == target) {
			while (vect[mi + 1] == target) ++mi;
			return mi + 1;
		} else if (vect[mi] > target) {
			hi = mi - 1;
			mi = lo + (hi - lo) / 2;
		} else {
			lo = mi + 1;
			mi = lo + (hi - lo) / 2;
		}
	}

	if (mi > vect.size() - 1) return vect.size();

	if (vect[mi] < target) {
		while (vect[mi] < target) {
			++mi;
			cout << vect[mi] << endl;
		}
 		--mi;
	} else {
		while (vect[mi] > target) --mi;
	}

	return mi + 1;
}

int binarySearch2 (vector<int> &vect, int target) {
	int lo = 0, hi = vect.size(), mi;

	while (lo <= hi) {
		mi = lo + (hi - lo) / 2;
		if (vect[mi] == target) {
			while (vect[mi + 1] == target) --mi;
			return mi + 1;
		} else if (vect[mi] > target) {
			hi = mi - 1;
			mi = lo + (hi - lo) / 2;
		} else {
			lo = mi + 1;
			mi = lo + (hi - lo) / 2;
		}
	}

	if (mi < 0) return 1;

	if (vect[mi] < target) {
		while (vect[mi] < target) ++mi;
	} else {
		while (vect[mi] > target) --mi;
		++mi;
	}

	return mi + 1;
}

int main() {

	ifstream fi("cautbin.in");
	ofstream fo("cautbin.out");
	vector<int> vect;
	int n, x, noTasks;
	vector<pair<int, int> > tasks;

	fi >> n;

	for (int i = 0; i < n; ++i) {
		fi >> x;
		vect.push_back(x);
	}

	fi >> noTasks;

	for (int i = 0; i < noTasks; ++i) {
		pair<int, int> aux;

		fi >> aux.first;
		fi >> aux.second;

		tasks.push_back(aux);
	}

	for (int i = 0; i < noTasks; ++i) {
		if (tasks[i].first == 0) {
			fo << binarySearch(vect, tasks[i].second) << endl;
		} else if (tasks[i].first == 1) {
			fo << binarySearch1(vect, tasks[i].second) << endl;
		} else {
			fo << binarySearch2(vect, tasks[i].second) << endl;
		}
	}



	fo.close();
	fi.close();

	return 0;
}