#include <bits/stdc++.h>
using namespace std;

int v[100000];

int binary_search(int len, int action, int x) {
	int left = 0, right = len - 1;
	while (left < right) {
		int mid = 1 + left + (right - left) / 2;
		if (action == 2) {
			mid = left + (right - left) / 2;
			if (v[mid] < x) {
				left = mid + 1;
			} else {
				right = mid;
			}
			continue;
		}
		if (v[mid] > x) {
		    right = mid - 1;
		} else {
		    left = mid;
		}
	}
	if (action == 2 && v[left] >= x) {
		return left;
	}
	if (action == 1 && v[right] <= x) {
		return right;
	}
	if (action == 0 && v[right] == x) {
		return right;
	} else {
		return -1;
	}
}

int main() {
	ifstream cin("cautbin.in");
	ofstream cout("cautbin.out");
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> v[i];
	}
	int m;
	cin >> m;
	for (int j = 0; j < m; ++j) {
		short action, x;
		cin >> action >> x;
		int rez = binary_search(n, action, x);
		cout << rez + 1 << "\n";
	}
	cout.close();
	return 0;
}