#include <iostream>
#include <fstream>
#include <math.h>

using namespace std;

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

int cerinta_0(int sir[], int N, int valoare){
	int lo = 0, hi = N - 1, mij, pozitie = 0;
	int vec_pozitie[N + 1], cnt = 0;

	while(lo <= hi){
		mij = lo + (hi - lo) / 2;
		if(valoare == sir[mij]){
			vec_pozitie[cnt] = mij;
			cnt++;
			lo = mij + 1;
		}
		else if (valoare < sir[mij]){
			hi = mij - 1;
		}
		else{
			lo = mij + 1;
		}
	}
	if(cnt != 0){
		pozitie = vec_pozitie[cnt - 1] + 1;
	}
	else{
		pozitie = -1;
	}

	return pozitie;
}

unsigned int cerinta_1(int sir[], int N, int valoare){
	int lo = 0, hi = N - 1, mij, pozitie = 0;
	int vec_pozitie[N + 1], cnt = 0;

	while(lo <= hi){
		mij = lo + (hi - lo) / 2;
		if(valoare >= sir[mij]){
			vec_pozitie[cnt] = mij;
			cnt++;
			lo = mij + 1;
		}
		else{
			hi = mij - 1;
		}
	}

	pozitie = vec_pozitie[cnt - 1] + 1;

	return pozitie;
}

unsigned int cerinta_2(int sir[], int N, int valoare){
	int lo = 0, hi = N - 1, mij, pozitie = 0;
	int vec_pozitie[N + 1], cnt = 0;

	while(lo <= hi){
		mij = lo + (hi - lo) / 2;
		if(valoare <= sir[mij]){
			vec_pozitie[cnt] = mij;
			cnt++;
			hi = mij - 1;
		}
		else{
			lo = mij + 1;
		}
	}
	pozitie = vec_pozitie[cnt - 1] + 1;

	return pozitie;
}

int main() {
  int sir[100000], N, valoare, cazuri, cerinta;
	fin >> N;
	for(int i = 0; i < N; ++i){
		fin >> sir[i];
	}
	fin >> cazuri;
	int vector_poz[cazuri + 1];
	for(int i = 0; i < cazuri; ++i){
		fin >> cerinta >> valoare;
		if(cerinta == 0){
			vector_poz[i] = cerinta_0(sir, N, valoare);
		}
		else if(cerinta == 1){
			vector_poz[i] = cerinta_1(sir, N, valoare);
		}
		else if(cerinta == 2){
			vector_poz[i] = cerinta_2(sir, N, valoare);
		}
	}
	for(int i = 0; i < cazuri; ++i){
		fout << vector_poz[i] << "\n";
	}

    return 0;
}