#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

//int lo, hi, p;
int mid, l=0, h;
vector <int> v;

int cerinta1(int lo, int hi, int p);
int cerinta2(int lo, int hi, int p);
int cerinta3(int lo, int hi, int p);

int main()
{
    ifstream f("cautbin.in");
    ofstream g("cautbin.out");
	int n, in, caz, intrebari, nr_de_cautat;
	f >> n;
	for (int i = 1; i <= n; i++)
	{
		f >> in;
		v.push_back(in);
	}
	l = 0;
	h = v.size()-1;
	f >> intrebari;
	for (int i = 1; i <= intrebari; i++)
	{
		f >> caz;
		f >> nr_de_cautat;
		switch (caz)
		{
		case 0:
        {
			g << cerinta1(l, h, nr_de_cautat)<<'\n';
		} break;

		case 1:
        {
            g<<cerinta2(l, h, nr_de_cautat)<<'\n';
		} break;

		case 2:
        {
			g<<cerinta3(l, h, nr_de_cautat)<<'\n';
		} break;
		}
	}



    return 0;
}

int cerinta1(int lo, int hi, int p)
{
	while (lo < hi)
	{
		mid = lo + (hi - lo + 1) / 2;
		if (v[mid] == p)
		{
			lo = mid;
		}
		else
		{
			hi = mid - 1;
		}
	}

	if (v[lo] == p)
	{
		return lo + 1;
	}
	else return -1;
}

int cerinta2(int lo, int hi, int p)
{
	while(lo<hi)
    {
        mid = lo + (hi - lo + 1) / 2;
		if (v[mid] <= p)
		{
			lo = mid;
		}
		else
		{
			hi = mid - 1;
		}
    }

        return lo+1;

}

int cerinta3(int lo, int hi, int p)
{
	while (lo < hi)
	{
		mid = lo + (hi - lo) / 2;
		if (v[mid] >= p)
		{
			hi = mid;
		}
		else
		{
			lo = mid + 1;
		}
	}

	return lo + 1;

}