// infoarenaBinarySearch.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"
#include <fstream>
#include <assert.h>

#define MaxN 100005

using namespace std;

int v[MaxN];

int N;
int bs1(int val) {
	int l = 1, u = N;
	while (l < u) {
		int m = l + (u - l) / 2;
		if (v[m] <= val) {
			l = m + 1;
		}
		else {
			u = m;
		}
	}

	assert(1 <= l && l <= N);

	return v[l - 1] == val ? l - 1 : -1;
}

int bs2(int val) {
	int l = 1, u = N;
	while (l < u) {
		int m = l + (u - l) / 2 + 1;
		if (v[m] > val) {
			u = m - 1;
		}
		else {
			l = m;
		}
	}

	assert(v[l] <= val && 1 <= l && l <= N);

	return l;
}

int bs3(int val) {
	int l = 1, u = N;
	while (l < u) {
		int m = l + (u - l) / 2;
		if (v[m] < val) {
			l = m + 1;
		}
		else {
			u = m;
		}
	}

	assert(v[l] >= val && 1 <= l && l <= N);

	return l;
}

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int main()
{
	fin >> N;

	for (int i = 1; i <= N; ++i) {
		fin >> v[i];
	}

	int M;
	fin >> M;

	for (int m = 1; m <= M; ++m) {
		int operationType, value;
		fin >> operationType >> value;

		if (operationType == 0) {
			fout << bs1(value) << "\n";
		}
		else if (operationType == 1) {
			fout << bs2(value) << "\n";
		}
		else {
			fout << bs3(value) << "\n";
		}
	}

    return 0;
}