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

int bs0(int target, const vector<int> &v)
{
	int i, step, n = v.size() - 1;
	for (step = 1; step <= n; step <<= 1);
	for (i = 0; step; step >>= 1)
		if (i + step <= n && v[i + step] <= target)
			i += step;
	return v[i] == target && i ? i : -1;
}

int bs1(int target, const vector<int> &v)
{
	int i, step, n = v.size() - 1;
	for (step = 1; step <= n; step <<= 1);
	for (i = 0; step; step >>= 1)
		if (i + step <= n && v[i + step] <= target)
			i += step;
	return i;
}

int bs2(int target, const vector<int> &v)
{
	int i, step, n = v.size() - 1;
	for (step = 1; step <= n; step <<= 1);
	for (i = n; step; step >>= 1)
		if (i - step >= 1 && v[i - step] >= target)
			i -= step;
	return i;
}

int main()
{
	ifstream fin("cautbin.in");
	ofstream fout("cautbin.out");
	int n;
	fin >> n;
	vector<int> v(n + 1);
	for (int i = 1; i <= n; ++i)
		fin >> v[i];
	int q;
	fin >> q;
	while (q--) {
		int code, target;
		fin >> code >> target;
		if (code == 0)
			fout << bs0(target, v) << '\n';
		else if (code == 1)
			fout << bs1(target, v) << '\n';
		else if (code == 2)
			fout << bs2(target, v) << '\n';
	}
}