#include <iostream>
#include <vector>
#include <fstream>
 
#define TYPE_0 0
#define TYPE_1 1
#define TYPE_2 2
#define NOT_FOUND -1
 
int binary_search0(const std::vector<int>& V, int left, int right, int x)
{
    int last = 0;
    for (; left <= right; ) {
        int mid = left + (right - left) / 2;
        if (V[mid] <= x) {
            last = mid;
            left = mid + 1;
        } else right = mid - 1;
    }
 
    if (V[last] == x) return last + 1;
    else return NOT_FOUND; 
}
 
int binary_search1(const std::vector<int>& V, int left, int right, int x)
{
    int last = 0;
    for (; left <= right; ) {
        int mid = left + (right - left) / 2;
        if (V[mid] <= x) {
            last = mid;
            left = mid + 1;
        } else right = mid - 1;
    }
     
    return last + 1;
}
 
int binary_search2(const std::vector<int>& V, int left, int right, int x)
{
    int last = 0;
    for (; left <= right; ) {
        int mid = left + (right - left) / 2;
        if (V[mid] >= x) {
            last = mid;
            right = mid - 1;
        } else left = mid + 1;
    }
 
    return last + 1;
}
 
int main()
{
    std::ios_base::sync_with_stdio(false);

    std::ifstream in("cautbin.in");
    std::ofstream out("cautbin.out");
 

    int N;
    in >> N;
 
    std::vector<int> V(N);
    for (int i = 0; i < N; i++) {
        in >> V[i];
    }
 
    int op_number;
    in >> op_number;
    int op_type, x;
    for (int operation = 1; operation <= op_number; operation++) {
 
        in >> op_type >> x;
        switch(op_type) {
            case TYPE_0 :
                out << binary_search0(V, 0, V.size() - 1, x) << "\n";
                break;
            case TYPE_1 :
                out << binary_search1(V, 0, V.size() - 1, x) << "\n";
                break;
            case TYPE_2 :
                out << binary_search2(V, 0, V.size() - 1, x) << "\n";
                break;
            default :
                std::cout << "Don't give me stupid indexes\n";
        }
 
    }
 
    return 0;
}