#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;
	fin >> t;
	for (int i = 1; i <= t; i++) {
		fin >> k >> x;
		left = 0;
		right = n - 1;
		poz = -1;

		if (k == 0) {
			while (left <= right) {
				middle = (left + right) / 2;

				if (nums[middle] == x) {
					poz = middle + 1;
					break;
				}
				else {
					if (nums[middle] < x)
						left = middle + 1;
					else
						right = middle - 1;
				}
			}
		}
		else if (k == 1) {
			while (left <= right) {
				middle = (left + right) / 2;
				if (nums[middle] <= x) {
					left = middle + 1;
					poz = middle;
				}
				else
					right = middle - 1;
			}
		}
		else {
			while (left <= right) {
				middle = (left + right) / 2;
				if (nums[middle] >= x) {
					right = middle - 1;
					poz = middle;
				}
				else
					left = middle + 1;
			}
		}

		if (poz != -1)
			fout << poz + 1 << '\n';
		else
			fout << poz << '\n';
	}


	return 0;
}