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

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;
}

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;
}

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;
}

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;
}