#include <fstream>

using namespace std;

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

int cautbin0(unsigned v[100000] , unsigned min , unsigned max , unsigned x ) {
	
	unsigned mid ;
	
	while (min < max) {
		
		mid = (min + max) / 2;
		
		if(v[mid] <= x)
			min = mid + 1;
		
		else
			max = mid - 1;
	}
	
	mid = (max + min) / 2;
	
	if(v[mid] > x)
		--mid;
	if(v[mid] == x)
		return mid;
	
	else return -1;
}

unsigned cautbin1(unsigned v[100000] , unsigned min , unsigned max , unsigned x ) {
	
	unsigned mid ;
	
	while (min < max) {
		
		mid = (min + max) / 2;
		
		if(v[mid] <= x)
			min = mid + 1;
		
		else
			max = mid;
	}
	
	mid = (min + max) / 2;
	
	if(v[mid] > x)
		mid--;
	return mid;
	
}

unsigned cautbin2(unsigned v[100000] , unsigned min , unsigned max , unsigned x ) {
	
	unsigned mid ;
	
	while (min < max) {
		
		mid = (min + max) / 2;
		
		if(v[mid] < x)
			min = mid + 1;
		
		else
			max = mid;
	}
	
	mid = (min + max) / 2;
	
	if(v[mid] < x)
		++mid;
	return mid;
	
}
int main() {
	
	unsigned n , v[100000] , M , m1[100000] , m2[100000] , i , j;
	
	fin >> n; // numarul de valori din vector
	
	for( i = 1 ; i <= n ; i++)
		fin >> v[i];
	
	fin >> M; // numar de intrebari
	
	// pe linia 0 vor fi puse tipurile de intrebari 
	// pe linia 1 vor fi puse valorile de cautat
		for( j = 1 ; j <= M ; j++){
			fin >> m1[j];
			fin >> m2[j];
		}
	
	for(j = 1 ; j <= M ; j++) {
		
		if(m1[j] == 0)//fout << m2[j] << " ";
			fout << cautbin0(v , 0 , n , m2[j]) << "\n";
		
		else if(m1[j] == 1)//fout << m2[j] << " ";
			fout << cautbin1(v , 0 , n , m2[j]) << "\n";
		
		else //fout << m2[j] << " ";
			fout << cautbin2(v , 0 , n , m2[j]) << "\n";
	
	}
	
	return 0;
}