#include <iostream>
#include <fstream>
using namespace std;

const int MAX_SIZE = 100000;

int cautbin0(int a[], int n, int x){
	int st = 1, dr = n, mij;
	while (st <= dr) {
		mij = (st + dr) / 2;
		if (a[mij] <= x) {
			st = mij + 1;
		} else {
			dr = mij - 1;
		}
	}
	mij = (st + dr) / 2;

	if (a[mij] > x) mij--;
	if (a[mij] == x) return mij;
	return -1;
} 
int cautbin1(int a[], int n, int x){
	int st = 1, dr = n, mij;
	while (st < dr){
		mij = (st + dr) / 2;
		if (a[mij] <= x) {
			st = mij + 1;
		} else {
			dr = mij;
		}
	}
	mij = (st + dr) / 2;
	if (a[mij] > x) --mij;
	return mij;
}
int cautbin2(int a[], int n, int x){
	int st = 1, dr = n, mij;
	while (st < dr){
		mij = (st + dr) / 2;
		if (a[mij] < x){
			st = mij + 1;
		} else {
			dr = mij;
		}
	}
	mij = (st + dr) / 2;
	if (a[mij] < x) ++mij;
	return mij;
}

int main() {
	ifstream fin("cautbin.in");
	ofstream fout("cautbin.out");
	int n;
	fin >> n;
	int v[n];
	for (int i = 1; i <= n; i++){
		fin >> v[i];
	}
	int m;
	fin >> m;
	int intrebare, x;
	int raspunsuri[MAX_SIZE];
	for (int i = 1; i <= m; i++){
		fin >> intrebare >> x;
		if (intrebare == 0){
			raspunsuri[i] = cautbin0(v, n, x);
		} else if (intrebare == 1){
			raspunsuri[i] = cautbin1(v, n, x);
		} else if (intrebare == 2){
			raspunsuri[i] = cautbin2(v, n, x);
		}
	}
	for (int i = 1; i <= m; i++){
		fout << raspunsuri[i] << endl;
	}
}