#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;
    while(l <= r) {
        mid = (l + r) / 2;
        if(v[mid] == x) {
            while(mid < v.size() - 1 && v[mid + 1] == x) {
                mid++;
            }
            return mid + 1;
        } else if(v[mid] < x) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return -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;
    while (l <= r) {
        mid = (l + r) / 2;
        if(v[mid] == x) {
            while(mid < v.size() - 1 && v[mid + 1] == x) {
                mid++;
            }
            return mid + 1;
        } else if(v[mid] < x) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    return r + 1; // daca x nu exista in sir, inseamna ca r + 1 e cea mai mare pozitie <= x
}

int caut_bin_2(std::vector<int>& v, int x) { // cea mai mica poz pt >= x
    int l = 0, r = v.size() - 1, mid;
    while (l <= r) {
        mid = (l + r) / 2;
        if(v[mid] == x) {
            while(mid > 0 && v[mid - 1] == x) {
                mid--;
            }
            return mid + 1;
        } else if(v[mid] < x) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }
    return l + 1; // daca x nu exista in sir, inseamna ca l + 1 e cea mai mica pozitie >= x
}

int main() {

    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");

    int n, m, nr, x;
    std::vector<int> v;
    fin >> n;
    v.resize(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;
}