#include <fstream>
#include <assert.h>

int binary_search(int n, int v[], int x) {
	int left = 1, middle, right = n;

	while (left <= right) {
		middle = left + (right - left) / 2;

		if (v[middle] <= x) {
			left = middle + 1;
		} else {
			right = middle - 1;
		}
	}

	middle = left + (right - left) / 2;

	if (v[middle] > x) {
		--middle;
	}

	if (v[middle] == x) {
		return middle;
	}

	return -1;
}

int lower_bound(int n, int v[], int x) {
	int left = 1, middle, right = n;

	while (left < right) {
		int middle = left + (right - left) / 2;

		if (v[middle] < x) {
			left = middle + 1;
		} else {
			right = middle;
		}
	}

	middle = left + (right - left) / 2;

	if (v[middle] < x) {
		++middle;
	}

	return middle;
}

int upper_bound(int n, int v[], int x) {
	int left = 1, middle, right = n;

	while (left < right) {
		middle = left + (right - left) / 2;

		if (v[middle] < x) {
			left = middle + 1;
		} else {
			right = middle;
		}
	}


	middle = left + (right - left) / 2;

	if (v[middle] > x) {
		--middle;
	}

	return middle;
}

 
int main() {	
	std::ifstream cin("cautbin.in");
	std::ofstream cout("cautbin.out");
	std::ios::sync_with_stdio(false);
	int n, m, x, t;

	cin >> n;
	assert(1 <= n && n <= 100000);
	int v[n];

	for (int i = 1 ; i <= n ; ++i) {
		cin >> v[i];
	}

	cin >> m;
	assert(1 <= m && m <= 100000);

	for (; m ; --m) {
		cin >> t >> x;
		switch(t) {
			case 0:	cout << binary_search(n, v, x) << '\n'; break;
			case 1: cout << upper_bound(n, v, x) << '\n'; break;
			case 2:	cout << lower_bound(n, v, x) << '\n'; break;
			default: break;
		}
	}
	
	return 0;
}