#include <algorithm>
#include <fstream>
#include <iterator>
#include <vector>

int lowerbound(const int x, const std::vector<int> &V);
int upperbound(const int x, const std::vector<int> &V);
int binarysearch(const int x, const std::vector<int> &V);

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

    int n;
    fin >> n;

    std::vector<int> V;
    std::copy_n(std::istream_iterator<int>(fin), n, std::back_inserter(V));

    int m, op, x;
    fin >> m;
    while (m--)
    {
        fin >> op >> x;
        switch (op)
        {
        case 1:
            fout << upperbound(x, V) << '\n';
            break;
        case 2:
            fout << lowerbound(x, V) + 1 << '\n';
            break;
        default:
            fout << binarysearch(x, V) << '\n';
        }
    }

    return 0;
}

int binarysearch(const int x, const std::vector<int> &V)
{
    int p = upperbound(x, V) - 1;

    if (p > 0 && V[p] == x)
        return p + 1;
    return -1;
}

int upperbound(const int x, const std::vector<int> &V)
{
    int lo{0}, hi{V.size()}, m;

    while (lo < hi)
    {
        m = lo + (hi - lo) / 2;

        if (V[m] <= x)
            lo = m + 1;
        else
            hi = m;
    }

    return lo;
}

int lowerbound(const int x, const std::vector<int> &V)
{
    int lo{0}, hi{V.size()}, m;

    while (lo < hi)
    {
        m = lo + (hi - lo) / 2;

        if (V[m] < x)
            lo = m + 1;
        else
            hi = m;
    }

    return lo;
}