#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;
		}
	}
	if (a[st] == x) {
		while (a[st + 1] == x) {
			st++;
		}
		return st;
	} else {
		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;
		}
	}
	if (a[st] <= x) {
		while (a[st + 1] <= x) {
			st++;
		}
		return st;
	} else {
		return -1;
	}
}
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;
		}
	}
	if (a[st] >= x){
		while (a[st - 1] >= x){
			st--;
		}
		return st;
	} else {
		return -1;
	}
}

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;
	}
}