#include <fstream>
#include <iostream>
using namespace std;

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

// cea mai mare pozitie pe care se afla un element cu valoarea target_value sau -1 daca aceasta valoare nu se gaseste in sir
int binary_search_0(int n, int arr[100001], int target_value) {
	int left = 1, right = n, pos = -1;
	while (left <= right) {
		int mid = left + (right - left) / 2;
		if (arr[mid] <= target_value) {
			pos = mid;
			left = mid + 1;
		} else {
			right = mid - 1;
		}
	}
	if (arr[pos] == target_value) {
		return pos;
	}
	return -1;
}

//cea mai mare pozitie pe care se afla un element cu valoarea mai mica sau egala cu target_value in sir. Se garanteaza ca cel mai mic numar al sirului este mai mic sau egal decat target_value
int binary_search_1(int n, int arr[100001], int target_value) {
	int left = 1, right = n, pos;
	while (left <= right) {
		int mid = left + (right - left) / 2;
		if (arr[mid] <= target_value) {
			left = mid + 1;
			pos = mid;
		} else {
			right = mid - 1;
		}
	}
	return pos;
}

// cea mai mica pozitie pe care se afla un element cu valoarea mai mare sau egala cu target_value in sir. Se garanteaza ca cel mai mare numar din sir este mai mare sau egal decat target_value
int binary_search_2(int n, int arr[100001], int target_value) {
	int left = 1, right = n, pos;
	while (left <= right) {
		int mid = left + (right - left) / 2;
		if (arr[mid] >= target_value) {
			right = mid - 1;
			pos = mid;
		} else {
			left = mid + 1;
		}
	}
	return pos;
}

int main() {
	int length, arr[100001] = { 0 };
	fin >> length;
	for (int i = 1; i <= length; ++i) {
		fin >> arr[i];
	}
	int nr_questions, question_type, target_value;
	fin >> nr_questions;
	while (nr_questions--) {
		fin >> question_type >> target_value;
		if (question_type == 0) {
			fout << binary_search_0(length, arr, target_value) << '\n';
		} else if (question_type == 1) {
			fout << binary_search_1(length, arr, target_value) << '\n';
		} else {
			fout << binary_search_2(length, arr, target_value) << '\n';
		}
	}
	return 0;
}