#include <fstream>
#include <vector>

typedef std::vector<int> IntVec;

void ReadArray(std::ifstream& fin, IntVec& a);
void SolveQuerries(std::ifstream& fin, const IntVec& a);
int BinarySearch1(const IntVec& a, int value);
int BinarySearch2(const IntVec& a, int value);
int BinarySearch3(const IntVec& a, int value);

int main()
{
    IntVec a;
    std::ifstream fin{ "cautbin.in" };

    ReadArray(fin, a);
    SolveQuerries(fin, a);

    return 0;
}

void ReadArray(std::ifstream& fin, IntVec& a)
{
    size_t n;
    fin >> n;

    a.reserve(n);

    int value;

    while (n--)
    {
        fin >> value;
        a.push_back(value);
    }
}

void SolveQuerries(std::ifstream& fin, const IntVec& a)
{
    std::ofstream fout{ "cautabin.out" };

    size_t n, querryType;
    int value;

    fin >> n;
    while (n--)
    {
        fin >> querryType >> value;

        switch (querryType)
        {
        case 0: fout << BinarySearch1(a, value) << '\n'; break;
        case 1: fout << BinarySearch2(a, value) << '\n'; break;
        case 2: fout << BinarySearch3(a, value) << '\n'; break;
        }
    }
}

int BinarySearch1(const IntVec& a, int value)
{
    int left{ 0 }, right{ static_cast<int>(a.size() - 1) }, middle{ 0 };

    while (left < right)
    {
        middle = (left + right) / 2;

        if (value == a[middle])
        {
            while (a[middle] == value && middle < static_cast<int>(a.size()))
            {
                ++middle;
            }
            return middle;
        }
        else if (value < a[middle])
        {
            right = middle - 1;
        }
        else
        {
            left = middle + 1;
        }
    }
    return -1;
}

int BinarySearch2(const IntVec& a, int value)
{
    int left{ 0 }, right{ static_cast<int>(a.size() - 1) }, middle{ 0 };

    while (left < right)
    {
        middle = (left + right) / 2;

        if (a[middle] > value)
            right = middle - 1;
        else
            left = middle + 1;
    }

    while (a[middle] <= value)
        ++middle;

    return middle;
}

int BinarySearch3(const IntVec& a, int value)
{
    int left{ 0 }, right{ static_cast<int>(a.size() - 1) }, middle{ 0 };

    while (left < right)
    {
        middle = (left + right) / 2;

        if (a[middle] > value)
            right = middle - 1;
        else
            left = middle + 1;
    }

    while (a[middle] >= value)
        --middle;

    return middle;
}