#include <fstream>
using namespace std;

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

int binary_search(int n, int arr[100001], int target_value) {
	int left = 1, right = n;
	while (left <= right) {
		int mid = left + (right - left) / 2;
		if (arr[mid] == target_value) {
			return mid;
		} else if (arr[mid] > target_value) {
			right = mid - 1;
		} else {
			left = mid + 1;
		}
	}
	return -1;
}

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;
		int pos = binary_search(length, arr, target_value);
		if (question_type == 0) {
			if (pos == -1) {
				fout << pos << '\n';
				continue;
			} else {
				int biggest_position = pos;
				for (int i = pos + 1; i <= length; ++i) {
					if (arr[i] == target_value) {
						biggest_position = i;
					} else {
						break;
					}
				}
				fout << biggest_position << '\n';
				continue;
			}
		} else if (question_type == 1) {
			if (pos == -1) {
				int biggest_position = 1;
				for (int i = 2; i <= length; ++i) {
					if (arr[i] < target_value) {
						biggest_position = i;
					} else {
						break;
					}
				}
				fout << biggest_position << '\n';
				continue;
			} else {
				int biggest_position = pos;
				for (int i = pos + 1; i <= length; ++i) {
					if (arr[i] == target_value) {
						biggest_position = i;
					}
					else {
						break;
					}
				}
				fout << biggest_position << '\n';
				continue;
			}
		} else {
			if (pos == -1) {
				int smallest_position = 1;
				for (int i = 1; i <= length; ++i) {
					if (arr[i] > target_value) {
						smallest_position = i;
						break;
					}
				}
				fout << smallest_position << '\n';
				continue;
			} else {
				int smallest_position = pos;
				for (int i = pos - 1; i >= 1; --i) {
					if (arr[i] == target_value) {
						smallest_position = i;
					} else {
						break;
					}
				}
				fout << smallest_position << '\n';
				continue;
			}
		}
	}
	return 0;
}