#include <iostream>

#define NMAX 100005

int first_search(int *arr, int n, int x)
{
    int l, r, m;
    
    l = 0;
    r = n - 1;

    while (l <= r) {
        m = l + ((r - l) >> 1);

        if (arr[m] <= x)
            l = m + 1;
        else
            r = m - 1;
    }

    if (r < 0 || arr[r] != x)
        return -1;

    return r;
}

int second_search(int *arr, int n, int x)
{
    int l, r, m;
    
    l = 0;
    r = n - 1;

    while (l <= r) {
        m = l + ((r - l) >> 1);

        if (arr[m] <= x)
            l = m + 1;
        else
            r = m - 1;
    }

    return r;
}

int third_search(int *arr, int n, int x)
{
    int l, r, m;
    
    l = 0;
    r = n - 1;

    while (l <= r) {
        m = l + ((r - l) >> 1);

        if (x <= arr[m])
            r = m - 1;
        else
            l = m + 1;
    }

    return l;
}


int main()
{
    int n, m;
    int arr[NMAX];

    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);

    std::cin >> n;

    for (int i = 0; i < n; ++i)
        std::cin >> arr[i];

    std::cin >> m;

    for (int q, x, p, i = 0; i < m; ++i)
    {
        std::cin >> q >> x;

        switch (q) {
        case 0:
            p = first_search(arr, n, x);

            std::cout << (p == -1 ? -1 : p + 1) << "\n";
            break;
        case 1:
            std::cout << second_search(arr, n, x) + 1 << "\n";
            break;
        case 2:
            std::cout << third_search(arr, n, x) + 1 << "\n";
            break;
        }
    }

    return 0;
}