#include <fstream>
#include <vector>
using namespace std;

// Căutare binară pentru query-ul 0: cea mai mare poziție cu valoarea x
int binarySearch0(vector<int>& v, int x) {
    int left = 0, right = v.size() - 1, result = -1;
    
    while (left <= right) {
        int mid = (left + right) / 2;
        if (v[mid] == x) {
            result = mid;
            left = mid + 1; // continuăm să căutăm mai la dreapta
        } else if (v[mid] < x) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return result;
}

// Căutare binară pentru query-ul 1: cea mai mare poziție cu valoarea <= x
int binarySearch1(vector<int>& v, int x) {
    int left = 0, right = v.size() - 1, result = -1;
    
    while (left <= right) {
        int mid = (left + right) / 2;
        if (v[mid] <= x) {
            result = mid;
            left = mid + 1; // continuăm să căutăm mai la dreapta
        } else {
            right = mid - 1;
        }
    }
    
    return result;
}

// Căutare binară pentru query-ul 2: cea mai mică poziție cu valoarea >= x
int binarySearch2(vector<int>& v, int x) {
    int left = 0, right = v.size() - 1, result = -1;
    
    while (left <= right) {
        int mid = (left + right) / 2;
        if (v[mid] >= x) {
            result = mid;
            right = mid - 1; // continuăm să căutăm mai la stânga
        } else {
            left = mid + 1;
        }
    }
    
    return result;
}

int main() {
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");
    
    int n, m;
    fin >> n;
    
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        fin >> v[i];
    }
    
    fin >> m;
    
    for (int i = 0; i < m; i++) {
        int tip, x;
        fin >> tip >> x;
        
        int result;
        if (tip == 0) {
            result = binarySearch0(v, x);
        } else if (tip == 1) {
            result = binarySearch1(v, x);
        } else { // tip == 2
            result = binarySearch2(v, x);
        }
        
        fout << result << "\n";
    }
    
    fin.close();
    fout.close();
    
    return 0;
}