#include <fstream>
using namespace std;

const int NMAX = 100002;

template <class T>
int upper_search(T a[], int N, T x)
{
	int ci = 0, I;
	for (I = 1; I < N; I <<= 1);
	do { if (ci + I < N) if (a[ci + I] <= x) ci += I; } while(I >>= 1);
	return ci;
}

template <class T>
int lower_search(T a[], int N, T x)
{
	int ci = N - 1, I;
	for (I = 1; I < N; I <<= 1);
	do { if (ci - I >= 0) if (a[ci - I] >= x) ci -= I; } while(I >>= 1);
	return ci;
}

int main()
{
	int N, m;
	int a[NMAX];
	ifstream f1("cautbin.in");
	freopen("cautbin.out", "w", stdout);
	f1 >> N;
	for (int i = 0; i != N; ++i) f1 >> a[i];
	f1 >> m;
	do {
		int o, x, r;
		f1 >> o >> x;
		switch(o) {
			case 0:
				r = upper_search(a, N, x);
				if (a[r] != x) printf("-1\n");
				else printf("%d\n", r + 1);
				break;
			case 1: printf("%d\n", upper_search(a, N, x) + 1); break;
			case 2: printf("%d\n", lower_search(a, N, x) + 1); break;
		}
	} while(--m);
	return 0;
}