#include <fstream>

#define MAX 100001

using namespace std;

/* Input example:
 * 
 * 5
 * 1 3 3 3 5
 * 1 
 * 0 3
 * 1 3
 * 
 * */

int N, M, value;
int numbers[MAX];

int first(int left, int right) {
    
    int m, pos = -2;
    while(left <= right){
        m =  left + (right - left)/2;
        if(numbers[m] == value){
            pos = m;
            left = m + 1;
        }else{
            if(numbers[m] < value)
                left = m + 1;
            else
                right = m - 1;
		}
    }
    return pos + 1;
}

int second(int left, int right){
    
    int m, pos = -1;
    while(left <= right){ 
        m = left + (right - left)/2;
        if(numbers[m] <= value){
            pos = m;
            left = m + 1;
        }else{
            right = m - 1;
        }
    }
    return pos + 1;
}

int third(int left, int right){
    int m, pos = -1;
    while(left <= right){
        m = left + (right - left)/2;
        if(numbers[m] >= value){
            pos = m;
            right = m - 1;
        }else{
            left = m  + 1;
        }
    }
    return pos + 1;
}

int main(){
	int query;	
	
	ifstream fin("cautbin.in");
	ofstream fout("cautbin.out");
	
	fin >> N;
	for(int i = 0; i < N; i++){
		fin >> numbers[i];
	}
	
	fin >> M;
	for(int i = 0; i < M; i++){
		fin >> query >> value;
		switch(query){
		case 0: fout << first(0, N-1) << "\n"; break;
		case 1: fout << second(0, N-1) << "\n"; break;
		case 2: fout << third(0, N-1) << "\n";
		}
	}
	return 0;
}