#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

const string FILE_NAME = "cautbin";
const string input = FILE_NAME + ".in";
const string output = FILE_NAME + ".out";

ifstream fin(input);
ofstream fout(output);

int main()
{
	unordered_map<int, bool>m;
	int n, t, k, x, left, right, middle, poz;
	fin >> n;
	vector<int>nums(n);
	for (int i = 0; i < n; i++)
		fin >> nums[i], m[nums[i]]=1;
	sort(nums.begin(), nums.end());
	fin >> t;
	for (int i = 1; i <= t; i++) {
		fin >> k >> x;
		left = 0;
		right = n - 1;
		poz = 1;

		if (k == 0) {
			if (m[x]) {
				while (left <= right) {
					middle = (left + right) / 2;
					if (nums[middle] <= x) {
						poz = middle;
						left = middle + 1;
					}
					else
						right = middle - 1;
				}
				fout << poz + 1 << '\n';
			}
			else {
				fout << -1 << '\n';
			}
		}
		else if (k == 1) {
			int poz=0;
			while (left <= right) {
				middle = (left + right) / 2;
				if (nums[middle] <= x) {
					poz = middle;
					left = middle + 1;
				}
				else
					right = middle - 1;
			}
			fout << poz + 1 << '\n';
		}
		else {
			int poz = 0;
			while (left <= right) {
				middle = (left + right) / 2;
				if (nums[middle] >= x) {
					right = middle - 1;
					poz = middle;
				}
				else
					left = middle + 1;
			}
			fout << poz + 1 << '\n';
		}
	}


	return 0;
}