# include <iostream>
# include <fstream>

# define INPUT_FILE_NAME "cautbin.in"
# define OUTPUT_FILE_NAME "cautbin.out"
# define MAX 100000

long N, M;
int arr[MAX];

long binary_search (int x, long ls, long ld) {
	if (ls > ld)
		return -1;
	long m = ls + (ld - ls) / 2;
	if (arr[m] == x)
		return m;
	else if (x > arr[m])
		return binary_search (x, m + 1, ld);
	else if (x < arr[m])
		return binary_search (x, ls, m - 1);
}
long case1 (int x) {
	long pos = binary_search (x, 0, N);
	if (pos == -1)
		return -1;
	while (pos < N && arr[pos] == x)
		pos ++;
	return pos;
}
long case2_helper (int x, long ls, long ld) {
	if (ls > ld)
		return ls;
	long m = ls + (ld - ls) / 2;
	if (arr[m] == x)
		return m;
	if (x > arr[m])
		return case2_helper (x, m + 1, ld);
	if (x < arr[m])
		return case2_helper (x, ls, m - 1);
}
long case2 (int x) {
	long pos = case2_helper (x, 0, N - 1);
	while (pos < N && arr[pos] <= x)
		pos ++;
	return pos;
}
long case3_helper (int x, long ls, long ld) {
	if (ls > ld)
		return ld;
	long m = ls + (ld - ls) / 2;
	if (arr[m] == x)
		return m;
	if (x > arr[m])
		return case3_helper (x, m + 1, ld);
	if (x < arr[m])
		return case3_helper (x, ls, m - 1);
}
long case3 (int x){
	long pos = case3_helper (x, 0, N - 1) + 1;
	if (arr[pos] != x)
		pos --;
	if (pos >= N)
		pos = N - 1;
	while (pos > 0 && arr[pos] > x)
		pos --;
	return pos;
}
int main (void) {
	std::fstream fin (INPUT_FILE_NAME, std::ios::in);
	std::fstream fout (OUTPUT_FILE_NAME, std::ios::out);
	fin >> N;
	for (int i = 0; i < N; i++)
		fin >> arr[i];
	fin >> M;
	int x, y;
	for (int i = 0; i < M; i++) {
		fin >> x >> y;
		if (x == 0)
			fout << case1 (y) << "\n";
		if (x == 1)
			fout << case2 (y) << "\n";
		if (x == 2)
			fout << case3 (y) - 1<< "\n";

	}
	fin.close ();
	fout.close ();
	return 0;
}