#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;
using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define NMAX 100001

int n, v[NMAX];

int search0(int);
int search1(int);
int search2(int);

int main()
{
	int i, m, type, x;
	ifstream fin("cautbin.in");
	ofstream fout("cautbin.out");

	fin >> n;
	for (i = 1; i <= n; ++i) fin >> v[i];

	for (fin >> m; m; --m)
	{
		fin >> type >> x;

		switch (type)
		{
		case 0:
			fout << search0(x) << '\n';
			break;

		case 1:
			fout << search1(x) << '\n';
			break;

		case 2:
			fout << search2(x) << '\n';
			break;
		}
	}

	fin.close();
	fout.close();

	return 0;
}

int search0(int x)
{
	int l, r, mid;

	for (l = 1, r = n; l < r; )
	{
		mid = (l + r + 1) / 2;

		if (v[mid] <= x) l = mid;
		else r = mid - 1;
	}

	return (v[l] == x ? l : -1);
}

int search1(int x)
{
	int l, r, mid;

	for (l = 1, r = n; l < r; )
	{
		mid = (l + r + 1) / 2;

		if (v[mid] <= x) l = mid;
		else r = mid - 1;
	}

	return l;
}

int search2(int x)
{
	int l, r, mid;

	for (l = 1, r = n; l < r; )
	{
		mid = (l + r) / 2;

		if (v[mid] < x) l = mid + 1;
		else r = mid;
	}

	return l;
}