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

using namespace std;

int cautbin_basic(vector<int> &v, int x) 
{
    int low = 0, high = v.size() - 1;

    while (low <= high) {
        int middle = (low + high) / 2;

        if (v[middle] < x) {
            low = middle + 1;
        } else if (v[middle] > x) {
            high = middle - 1;
        } else {
            return middle;
        }
    }

    return -1;
}

int cautbin_new_0(vector<int> &v, int x)
{
    int low = 0, high = v.size() - 1;

    while (low < high) {
        int middle = (low + high) / 2;

        if (v[high] == x) {
            return high + 1;
        }

        if (v[middle] < x) {
            low = middle + 1;
        } else if (v[middle] > x) {
            high = middle - 1;
        } else {
            low = middle;
            high -= 1;
        }
    }

    if (v[low] == x) {
        return low + 1;
    }

    return -1;
}

int cautbin_new_1(vector<int> &v, int x)
{
    int low = 0, high = v.size() - 1;

    while (low < high) {
        if (v[high] <= x) {
            low = high;
            break;
        }

        int middle = (low + high) / 2;

        if (low == middle) {
            break;
        }

        // cout << low << " " << middle << " " << high << endl;

        if (v[middle] > x) {
            high = middle - 1;
        } else {
            low = middle;
        }

    }

    return low + 1;
}

int cautbin_new_2(vector<int> &v, int x)
{
    int low = 0, high = v.size() - 1;

    while (low < high) {
        if (v[low] >= x) {
            high = low;
            break;
        }

        int middle = (low + high) / 2;

        if (high == middle) {
            break;
        }

        if (v[middle] < x) {
            low = middle + 1;
        } else {
            high = middle;
        }
    }

    return high + 1;
}

int main()
{
    ifstream in;
    ofstream out;

    in.open("cautbin.in");
    out.open("cautbin.out");

    int n;
    in >> n;
    vector<int> v(n);

    for (int i = 0; i < n; ++i)
        in >> v[i];

    int q;
    in >> q;

    int type, x;
    for (int i = 0; i < q; ++i)
    {
        in >> type >> x;

        switch (type)
        {
        case 0:
            out << cautbin_new_0(v, x) << '\n';
            break;
        case 1:
            out << cautbin_new_1(v, x) << '\n';
            break;
        case 2:
            out << cautbin_new_2(v, x) << '\n';
            break;
        }
    }

    in.close();
    out.close();
}