#include <fstream>
#include "BinSearch.h"

int binsearch(int[], int, int);
int binsearch_less(int[], int, int);
int binsearch_greater(int[], int, int);

int main() {
	std::ifstream fin("cautbin.in");
	std::ofstream fout("cautbin.out");

	int N;
	fin >> N;

	int* nums = new int[N];
	for (int i = 0; i < N; ++i) {
		fin >> nums[i];
	}

	int M;
	fin >> M;
	for (int i = 0; i < M; ++i) {
		int opt, x;
		fin >> opt >> x;
		switch (opt)
		{
		case 0: {
			int index = binsearch(nums, N, x);
			fout << (index == -1 ? -1 : index + 1) << '\n';
			break; }
		case 1:
			fout << binsearch_less(nums, N, x) + 1 << '\n';
			break;
		case 2:
			fout << binsearch_greater(nums, N, x) + 1 << '\n';
			break;
		}
	}
}

int binsearch(int nums[], int N, int x) {
	int pos = binsearch_less(nums, N, x);
	return nums[pos] == x ? pos : -1;
}

int binsearch_less(int nums[], int N, int x) {
	int index = 0;
	for (int step = 0; step < 30; ++step) {
		if (index + (1 << step) < N && nums[index + (1 << step)] <= x)
			index += (1 << step);
	}
	return nums[index] <= x ? index : 0;
}

int binsearch_greater(int nums[], int N, int x) {
	int index = N - 1;
	for (int step = 30; step >= 0; --step) {
		if (index - (1 << step) >= 0 && nums[index - (1 << step)] >= x)
			index -= (1 << step);
	}
	return nums[index] >= x ? index : N - 1;
}