#include <fstream>

using namespace std;

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

int cautbin0(int v[100000] , int min , int max , int x ) {
	
	int 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;
}

int cautbin1(int v[100000] , int min , int max , int x ) {
	
	int 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 cautbin2(int v[100000] , int min , int max , int x ) {
	
	int 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() {
	
	int n , v[100000] , M , i , a , b;
	
	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
	while(M--) { 
		fin >> a >> b;
		if(a == 0)
			fout << cautbin0(v , 0 , n , b) << "\n";
		if(a == 1)
			fout << cautbin1(v , 0 , n , b) << "\n";
		if(a == 2)
			fout << cautbin2(v , 0 , n , b) << "\n";
	}
	
	/*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;
}