#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>

using std::cout;
using std::cin;
using std::ifstream;
using std::ofstream;

/*
Se da un sir de numere ordonat crescator cu N elemente, si se cere sa se raspunda la M intrebari de tipul:
0 x - cea mai mare pozitie pe care se afla un element cu valoarea x sau -1 daca aceasta valoare nu se gaseste in sir
1 x - 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
2 x - 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 caut_bin_0(std::vector<int>& v, int x) { // cea mai mare poz pentru x, -1 altfel
    // int l = 0, r = v.size() - 1, mid, poz = -2;
    // while(l <= r) {
    //     mid = (l + r) / 2;
    //     if(v[mid] == x) {
    //         poz = mid;
    //         l = mid + 1; // cautam in dreapta
    //     } else if(v[mid] < x) {
    //         l = mid + 1;
    //     } else {
    //         r = mid - 1;
    //     }
    // }
    // return poz + 1;

    auto it = std::upper_bound(v.begin(), v.end(), x);
    if(it == v.begin() || *(it - 1) != x) {
        return -1; // x nu se gaseste in sir
    } else {
        return it - v.begin(); // pozitia lui x in sir
    }
}

int caut_bin_1(std::vector<int>& v, int x) { // cea mai mare poz pt <= x
    // int l = 0, r = v.size() - 1, mid, poz = -1;
    // while (l <= r) {
    //     mid = (l + r) / 2;
    //     if(v[mid] <= x) {
    //         poz = mid;
    //         l = mid + 1;
    //     } else { // v[mid] > x
    //         r = mid - 1;
    //     }
    // }
    // return poz + 1;

    auto it = std::upper_bound(v.begin(), v.end(), x);
    return (it - v.begin());
}

int caut_bin_2(std::vector<int>& v, int x) { // cea mai mica poz pt >= x
    // int l = 0, r = v.size() - 1, mid, poz = -1;
    // while (l <= r) {
    //     mid = (l + r) / 2;
    //     if(v[mid] >= x) {
    //         poz = mid;
    //         r = mid - 1;
    //     } else { // v[mid] < x
    //         l = mid + 1;
    //     }
    // }
    // return poz + 1;
    auto it = std::lower_bound(v.begin(), v.end(), x);
    return (it - v.begin() + 1);

}

int main() {

    ifstream fin("cautbin.in");
    if (!fin) { // Verificăm dacă fișierul de intrare s-a deschis corect
        std::cerr << "Eroare: Nu s-a putut deschide fisierul cautbin.in\n";
        return 1;
    }

    ofstream fout("cautbin.out");
    if (!fout) { // Verificăm dacă fișierul de ieșire s-a deschis corect
        std::cerr << "Eroare: Nu s-a putut deschide fisierul cautbin.out\n";
        return 1;
    }

    int n, m, nr, x;
    fin >> n;
    std::vector<int> v(n);
    for(int i = 0; i < n; i++) {
        fin >> v[i];
    }

    fin >> m;
    for(int i = 0; i < m; i++) {
        fin >> nr >> x;
        if (nr == 0)
            fout << caut_bin_0(v, x) << '\n';
        else if(nr == 1)
            fout << caut_bin_1(v, x) << '\n';
        else if(nr == 2)
            fout << caut_bin_2(v, x) << '\n';
    }

    return 0;
}