#include <iostream>
#include <fstream>

using namespace std;

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

int binarySearch1(int* a, int left, int right, int x ){

	int rez,rez1;
	if( left > right )
		return -1;
	else{
		int mid = left + ( right-left)/2;
		if( a[mid] == x ){
			 rez = mid;
			 rez1 = binarySearch1(a, mid+1, right,x);
		}
		else if( x < a[mid] )
			return binarySearch1( a, left, mid-1, x );
		else
			return binarySearch1( a, mid+1, right, x);
	}
	
		return rez < rez1 ? rez1 : rez ;
}

int binarySearch2( int* a, int left, int right ,int x ){

	int rez,rez1;
		if( left > right )
			return -1;
		else{
			int mid = left + (right-left)/2;
			if( a[mid] <= x ){
				rez = mid;
				rez1 = binarySearch2( a, mid+1, right, x );
			}
			else
				return binarySearch2( a, left, mid-1, x );
		}
		
		return rez < rez1 ? rez1 : rez;
}

int binarySearch3(int* v,int p, int u, int key) {
    int m;
 
    while (p < u) {
        m = (p + u) / 2;
        if (v[m] < key)
            p = m + 1;
        else
            u = m;
    }
 
    m = (p + u) / 2;
    if (v[m] < key)
       ++ m;
    return m;

}
int main(){
	
	int N, M, *a, cod, x;
	in >> N;
	a = new int[N];
	for( int i = 0 ; i < N; i++ )
		in >> a[i];
	in >> M;
	
	for( int i = 0; i < M; i++ ){
		in >> cod >> x;
		if( cod == 0 )
			out<< binarySearch1( a, 0, N-1, x)+1<<endl;
		else if( cod == 1 )
			out<< binarySearch2( a, 0, N-1, x)+1<<endl;
		else
			out<< binarySearch3( a, 0, N-1, x)<<endl;
	}
	
	return 0;
	
}