#include<fstream>
using namespace std;

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

int n, a[100000], r=-2, aux, st, dr, i, j, x, m;

void cautbin0(int n){
	st = 0;
	dr = n-1;
	r = -2;
	while(st < dr){
		aux = st + (dr - st)/2;
		if(x >= a[aux]) {
			r = aux;
			st = aux + 1;
		}
		else dr = aux;
	}
	if(st == dr && a[st]==x) r = st;	
}

void cautbin1(int n){
	st = 0;
	dr = n-1;
	r = -2;
	while(st < dr){
		aux = st + (dr - st)/2;
		if(x >= a[aux]){
		r = aux;
		st = aux+1;
		}
		else dr= aux;
	}
	if(st == dr && a[st]==x) r = st;	
}

void cautbin2(int n){
	st = 0;
	dr = n-1;
	r = -2;
	while(st < dr){
		aux = st + (dr - st)/2;
		if(x <= a[aux]){
			r = aux;
			dr = aux;
		}
		else st = aux+1;
	}
	if(st == dr && x==a[aux]) r = st;
}

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

	return 0;
}