#include <fstream>
using namespace std;

int v[100005], n, q;

int Bin0 (int x)
{
	int lo = 1, hi = n;
	while (lo <= hi)
	{
		int mid = (lo + hi) / 2;
		if (v[mid] == x)
		{
			while (v[mid+1] == x)
				mid++;
			return mid;
		}
		else
			if (v[mid] < x)
				lo = mid + 1;
		else
			hi = mid - 1;
	}
	return -1;
}

int Bin1 (int x)
{
	if (x >= v[n])
		return n;
	int lo = 1, hi = n, mid;
	while (lo < hi)
	{
		mid = (lo + hi) / 2;
		if (v[mid] == x)
		{
			while (v[mid+1] == x)
				mid++;
			return mid;
		}
		else
			if (v[mid] < x && x < v[mid+1])
				return mid;
		else
			if (v[mid] < x)
				lo = mid + 1;
		else
			if (v[mid+1] > x)
				hi = mid;
	}
	return -1;
}

int Bin2 (int x)
{
	if (x <= v[1])
		return 1;
	int lo = 1, hi = n + 1, mid;
	while (lo < hi)
	{
		mid = (lo + hi) / 2;
		if (v[mid] == x)
		{
			while (v[mid-1] == x)
				mid--;
			return mid;
		}
		else
			if (v[mid] < x && x < v[mid+1])
				return mid + 1;
		else
			if (v[mid] < x)
				lo = mid + 1;
		else
			if (v[mid+1] > x)
				hi = mid;
	}
	return -1;
}

int Bin (int t, int x)
{
	return (!t ? Bin0 (x) : (t == 1 ? Bin1 (x) : Bin2 (x)));
}

int main ()
{
	ifstream fin ("cautbin.in");
	fin >> n;
	for (int i = 1; i <= n; ++i)
		fin >> v[i];
	fin >> q;
	ofstream fout ("cautbin.out");
	for (int i = 0; i < q; ++i)
	{
		int t, nr;
		fin >> t >> nr;
		fout << Bin(t, nr) << "\n";
	}
	fin.close();
	fout.close();
	return 0;
}