#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;
	lastPos = 0;
	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;
			if (mid == 0)
			{
				if (a[0] == val)
					return mid;
				else 
					break;
			}
		}
		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)
			{
				while (lastPos > 0 && a[lastPos] > val)
				{
					lastPos--;
				}
				if (lastPos == n)
					lastPos -= 1;
				g << lastPos + 1 << '\n';
				continue;
			}
			while (tmp < n && a[tmp] == val)
				tmp++;
			g << tmp << '\n';
		}
		else
		{
			if (tmp == -1)
			{
				while (lastPos < n && a[lastPos] < val)
				{
					lastPos++;
				}
				if (lastPos == n)
					lastPos -= 1;
				g << lastPos + 1 << '\n';
				continue;
			}
			while (tmp >= 0 && tmp < n && a[tmp] == val)
				tmp--;
			if (tmp == n)
				g << tmp;
			else
				g << tmp + 2 << '\n';
		}
	}
	return 0;
}