#include <fstream>

#define MaxN 100005

using namespace std;

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

int v[MaxN], N, M, type, x;

int bin1() {
	int low = 0, high = N - 1;

	while (low <= high) {
		int mid = low + (high - low) / 2;
		if (v[mid] <= x)
			low = mid + 1;
		else
			high = mid - 1; 
	}

	if (v[high] > x)
		--high;
	if (v[high] != x)
		return -2;

	return high;
}

int bin2() {
	int low = 0, high = N - 1;

	while (low < high) {
		int mid = low + (high - low) / 2 + 1;
		if (v[mid] <= x)
			low = mid;
		else
			high = mid - 1;
	}

	return low;
}

int bin3() {
	int low = 0, high = N - 1;

	while (low < high) {
		int mid = low + (high - low) / 2;
		if (v[mid] >= x)
			high = mid;
		else
			low = mid + 1;
	}

	return low;
}


int main() {
	fin >> N;
	
	for (int i = 0; i < N; ++i)
		fin >> v[i];
	
	fin >> M;

	for (int m = 0; m < M; ++m) {
		fin >> type >> x;

		if (type == 0)
			fout << bin1() + 1;
		else if (type == 1)
			fout << bin2() + 1;
		else
			fout << bin3() + 1;

		fout << '\n';
	}

	return 0;
}