// INCORRECT VERSION
// !!! WORK HARD TO MAKE IT BETTER

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

#define TYPE_0 0
#define TYPE_1 1
#define TYPE_2 2

int binary_search0(const std::vector<int>& V, int left, int right, int x)
{
    if (left > right) return -1;
    int mid = left + (right - left) / 2;
    if (mid + 1 <= right && V[mid] == x && V[mid + 1] != x) return mid + 1;
    else if (x < V[mid]) return binary_search0(V, left, mid - 1, x);
    else return binary_search0(V, mid + 1, right, x);
}

int binary_search1(const std::vector<int>& V, int left, int right, int x)
{
    if (left > right) return 0;
    int mid = left + (right - left) / 2;
    if (mid + 1 <= right && V[mid] <= x && V[mid + 1] > x) return mid + 1;
    else if (x < V[mid]) return binary_search1(V, left, mid - 1, x);
    else return binary_search1(V, mid + 1, right, x);
}

int binary_search2(const std::vector<int>& V, int left, int right, int x)
{
    if (left > right) return 0;
    int mid = left + (right - left) / 2;
    if (mid - 1 >= 0 && V[mid] >= x && V[mid - 1] < x) return mid + 1;
    else if (x <= V[mid]) return binary_search2(V, left, mid - 1, x);
    else return binary_search2(V, mid + 1, right, x);
}

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

    int N;
    in >> N;

    std::vector<int> V;
    int elem;
    for (int i = 0u; i < N; i++) {
        in >> elem;
        V.push_back(elem);
    }

    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) << std::endl;
                break;
            case TYPE_1 :
                out << binary_search1(V, 0, V.size() - 1, x) << std::endl;
                break;
            case TYPE_2 :
                out << binary_search2(V, 0, V.size() - 1, x) << std::endl;
                break;
            default :
                std::cout << "Don't give me stupid index\n";
        }

    }

    return 0;
}