#include <iostream>
#include <fstream>
#include <vector>
#include <stdio.h>
#include <stdlib.h>

/* cea mai mare pozitie pe care se afla un element cu valoarea x
 sau -1 daca aceasta valoare nu se gaseste in sir */
int first_question(std::vector<int> &vector, int left, int right, int element) {
    int pivot;
    
    while (left <= right) {
        pivot = (left + right) / 2;
        
        if (element >= vector[pivot])
            left = pivot + 1;
        else
            right = pivot - 1;
    }
    
    pivot = (left + right) / 2;
    
    if (vector[pivot] > element)
        pivot--;
    if (vector[pivot] == element)
        return pivot;
    
    return -1;
}

/* cea mai mare pozitie pe care se afla un element cu valoarea mai mica
 sau egala cu x in sir. Se garanteaza ca cel mai mic numar al sirului
 este mai mic sau egal decat x */
int second_question(std::vector<int> &vector, int left, int right, int element) {
    int pivot;
    
    while (left < right) {
        pivot = (left + right) / 2;
        
        if (element >= vector[pivot])
            left = pivot + 1;
        else
            right = pivot;
    }
    
    pivot = (left + right) / 2;
    
    if (vector[pivot] > element)
        --pivot;
    
    return pivot;
}

/* cea mai mica pozitie pe care se afla un element cu valoarea
mai mare sau egala cu x in sir. Se garanteaza ca cel mai mare
numar din sir este mai mare sau egal decat x */
int third_question(std::vector<int> &vector, int left, int right, int element) {
    int pivot;
    
    while (left < right) {
        pivot = (left + right) / 2;
        
        if (element <= vector[pivot])
            right = pivot;
        else
            left = pivot + 1;
    }
    
    pivot = (left + right) / 2;
    
    if (vector[pivot] < element)
        ++pivot;
    
    return pivot;
}

int main() {
    std::ifstream in("cautbin.in");
    std::ofstream out("cautbin.out");
    
    // Read size of the vector
    int N;
    in >> N;
    
    // Read vector
    std::vector<int> vector(N);
    for (int i = 0; i < N; i++)
        in >> vector[i];
    
    // Read number of questions
    int M;
    in >> M;
    
    int question, element;
    while (M--){
        // Read questions
        in >> question;
        in >> element;
        
        // Call functions according to the type of question
        switch (question) {
            case 0:
                out << first_question(vector, 0, N -1 , element) << "\n";
                break;
            case 1:
                out << second_question(vector, 0, N-1, element) << "\n";
                break;
            case 2:
                out << third_question(vector, 0, N-1, element) << "\n";
                break;
            default:
                break;
        }
    }
    
    return 0;
}

//int main () {
//    int N, M, question, element;
//    
//    freopen("cautbin.in", "r", stdin);
//    freopen("cautbin.out", "w", stdout);
//    
//    scanf("%d", &N);
//    std::vector<int> vector(N);
//    for (int i = 1; i <= N; ++ i) {
//        scanf("%d", &vector[i]);
//    }
//    
//    scanf("%d", &M);
//    while (M--){
//        // Read questions
//        scanf("%d %d", &question, &element);
//
//        // Call functions according to the type of question
//        switch (question) {
//            case 0:
//                printf("%d\n", first_question(vector, 1, N, element));
//                break;
//            case 1:
//                printf("%d\n", second_question(vector, 1, N, element));
//                break;
//            case 2:
//                printf("%d\n", third_question(vector, 1, N, element));
//                break;
//        }
//    }
//    
//    return 0;
//}