#include<fstream>
#include<iostream>
#define MAX 100005
using namespace std;

ifstream f("cautbin.in");
ofstream g("cautbin.out");

int a[MAX], n, m, t, val;

int cautareBinara(int &lastPos)
{
	unsigned long long st = 0, dr = n, mid;
	while (st < dr)
	{
		mid = st + (dr - st) / 2;
		if (val == a[mid])
		{
			return mid;
		}
		if (val > a[mid])
		{
			st = mid + 1;
		}
		else
		{
			dr = mid - 1;
		}
		lastPos = mid;
	}
	return -1;
}

int main()
{
	int tmp,lastPos;
	f >> n;
	for (int i = 0; i < n; ++i)
	{
		f >> a[i];
	}
	f >> m;
	for (int i = 0; i < m; ++i)
	{
		f >> t >> val;
		tmp = cautareBinara(lastPos);
		if (t == 0)
		{
			if (tmp == -1)
			{
				g << -1 << '\n';
				continue;
			}
			while (tmp < n && a[tmp] == val)
				tmp++;
			g << tmp <<'\n';
		}
		else if (t == 1)
		{
			if (tmp == -1)
			{
				if (lastPos == n)
					g << lastPos;
				else
					g << lastPos + 1 << '\n';
				continue;
			}
			while (tmp < n && a[tmp] == val)
				tmp++;
			g << tmp << '\n';
		}
		else
		{
			if (tmp == -1)
			{
				if (lastPos == 0)
					g << lastPos;
				else
					g << lastPos + 1 << '\n';
				continue;
			}
			cout << tmp;
			while (tmp >= 0 && a[tmp] == val)
				tmp--;
			g << tmp + 2 << '\n';
		}
	}
	return 0;
}