// infoarenaDFSnonRec.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"
#include <fstream>

#define MaxN 100005

using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int N, M, op, x;
int val[MaxN];

int bsearch1(int x) {
	int low = 1, high = N;
	while (low < high) {
		int mid = low + (high - low) / 2;
		if (x < val[mid])
			high = mid;
		else
			low = mid + 1;
	}
	if (low > 1 && val[low - 1] == x)
		return low - 1;
	else
		return -1;
}

int bsearch2(int x) {
	int low = 1, high = N;
	while (low < high) {
		int mid = low + (high - low) / 2;
		if (x < val[mid])
			high = mid;
		else
			low = mid + 1;
	}
	return low - 1;
}

int bsearch3(int x) {
	int low = 1, high = N;
	while (low < high) {
		int mid = low + (high - low) / 2 + 1;
		if (x >= val[mid])
			high = mid - 1;
		else
			low = mid;
	}
	return low + 1;
}

int main() {
	fin >> N;

	for (int i = 1; i <= N; ++i)
		fin >> val[i];

	fin >> M;

	for (int i = 0; i < M; ++i) {
		fin >> op >> x;

		if (op == 0) {
			fout << bsearch1(x);
		}
		else if (op == 1) {
			fout << bsearch2(x);
		}
		else {
			fout << bsearch3(x);
		}
		fout << '\n';
	}

	return 0;
}