#include<fstream>
using namespace std;

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

int n, a[100000], r;

void cautbin0(int x, int st, int dr){
	if(st != dr){
		int aux;
		aux = (st + dr)/2;
		if(x >= a[aux]) {
			if(x == a[aux]) r = aux;
			cautbin0(x, aux+1, dr);
		}
		else if(x < a[aux]) cautbin0(x, st, aux);
	}
}

void cautbin1(int x, int st, int dr){
	if(st != dr){
		int aux;
		aux = (st + dr)/2;
		if(x >= a[aux]){
			r = aux;
			cautbin1(x, aux+1, dr);
		}
		else cautbin1(x, st, aux);
	}
}
void cautbin2(int x, int st, int dr){
	if(st != dr){
		int aux; 
		aux = (st + dr)/2;
		if(x <= a[aux]){
			r = aux;
			cautbin2(x, st, aux);
		}
		else cautbin2(x, aux+1, dr);
	}
}

int main(){
	
	int i, j, m, x;
	fin >> n;
	for(i=0; i<n; i++) fin >> a[i];
	fin >> m;
	for(i=0; i<m; i++){
		fin >> j >> x;
		r = -1;
		if(j == 0) {
			cautbin0(x, 0, n-1);
			fout << r<< endl;
		}
		else if(j == 1) {
			cautbin1(x, 0, n-1);
			fout << r<< endl;
		}
		else if(j == 2) {
			cautbin2(x, 0, n-1);
			fout << r << endl;
		}
	}
	
	fin.close();
	fout.close();
	
	return 0;
}