//#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 - left) / 2;
//        
//        if (element >= vector[pivot])
//            left = pivot + 1;
//        else
//            right = pivot - 1;
//    }
//    
//    pivot = left + (right - left) / 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 - left) / 2;
//        
//        if (element >= vector[pivot])
//            left = pivot + 1;
//        else
//            right = pivot;
//    }
//    
//    pivot = left + (right - left) / 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 - left) / 2;
//        
//        if (element <= vector[pivot])
//            right = pivot;
//        else
//            left = pivot + 1;
//    }
//    
//    pivot = left + (right - left) / 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, element) << "\n";
//                break;
//            case 1:
//                out << second_question(vector, 0, N, element) << "\n";
//                break;
//            case 2:
//                out << third_question(vector, 0, N, element) << "\n";
//                break;
//            default:
//                break;
//        }
//    }
//    
//    return 0;
//}

#define N 100010
//int v[N];

int bsearch0 (std::vector<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 - 1;
    }
    m = (p + u) / 2;
    
    if (v[m] > key) m --;
    if (v[m] == key)
        return m;
    return -1;
}

int bsearch1 (std::vector<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 bsearch2 (std::vector<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 i, n, m, tip, val;
    
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%d", &n);
    std::vector<int> vector(n);
    for (i = 1; i <= n; ++ i) {
        scanf("%d", &vector[i]);
//        vector[i] = aux
    }
    
    scanf("%d", &m);
    
    while (m --){
        scanf("%d%d", &tip, &val);
        if (tip == 0)
            printf("%d\n", bsearch0(vector, 1, n, val));
        if (tip == 1)
            printf("%d\n", bsearch1(vector, 1, n, val));
        if (tip == 2)
            printf("%d\n", bsearch2(vector, 1, n, val));
    }
    exit(0);
}