#include <iostream>
#include <fstream>
#include <cstdio>

using namespace std;

ofstream g;

void readfrom(int *n, int *m, int *a, int b[100002][2])
{
	ifstream f;
	f.open("cautbin.in");
	f >> *n;
	for (int i = 0; i < *n; i++)
		f >> a[i];
	f >> *m;
	for (int i = 0; i < *m; i++)
		f >> b[i][0] >> b[i][1];
	f.close();
}

void cautbin0(int *a, int n, int x)
{
	int i = 0, index = -1;
	while (i <= n)
	{
		int middle = (i + n) / 2;
		if (a[middle] == x) index = middle + 1;
		if (a[middle] > x) n = middle - 1; else i = middle + 1;
		//cout << i << ' ' << middle << ' ' << n << endl;
	}
	g << index << '\n';
}

void cautbin1(int *a, int n, int x)
{
	int i = 0, index = -1;
	while (i <= n)
	{
		int middle = (i + n) / 2;
		if (a[middle] <= x) index = middle + 1;
		if (a[middle] > x) n = middle - 1; else i = middle + 1;
		//cout << i << ' ' << middle << ' ' << n << endl;
	}
	g << index << '\n';
}

void cautbin2(int *a, int n, int x)
{
	int i = 0, index = -1;
	while (i <= n)
	{
		int middle = (i + n) / 2;
		if (a[middle] >= x) index = middle + 1;
		if (a[middle] < x) i = middle + 1; else n = middle - 1;
		//cout << i << ' ' << middle << ' ' << n << endl;
	}
	g << index << '\n';
}

int	main(void)
{
	int n, m, a[100002], b[100002][2];

	readfrom(&n, &m, a, b);
	g.open("cautbin.out");
	for (int i = 0; i < m; i++)
	{
		if (b[i][0] == 0) cautbin0(a, n, b[i][1]);
		if (b[i][0] == 1) cautbin1(a, n, b[i][1]);
		if (b[i][0] == 2) cautbin2(a, n, b[i][1]);
	}
	g.close();
	return (0);
}