#include <iostream>
#include <fstream>

int getLg(int n) {
    int lg;
    for (lg = 1; lg <= n; lg <<= 1);
    return lg;
}

int firstTask(int x, int lg, const int n, const int a[]) {
    int poz;
    for (poz = 0; lg != 0; lg >>= 1) {
        if (lg + poz < n && a[lg + poz] <= x) {
            poz += lg;
        }
    }
    if (a[poz] == x) {
        return poz + 1;
    }
    return -1;
}

int secondTask(int x, int lg, const int n, const int a[]) {
    int poz;
    for (poz = 0; lg != 0; lg >>= 1) {
        if (lg + poz < n && a[lg + poz] <= x) {
            poz += lg;
        }
    }
    return poz + 1;
}

int thirdTask(int x, int lg, const int n, const int a[]) {
    int poz;
    for (poz = n - 1; lg != 0; lg >>= 1) {
        if (poz - lg >= 0 && a[poz - lg] >= x) {
            poz -= lg;
        }
    }
    return poz + 1;
}

int main() {
    std::ifstream fin("cautbin.in");
    std::ofstream fout("cautbin.out");
    int n, a[100005];
    fin >> n;
    for (int i = 0; i < n; ++i) {
        fin >> a[i];
    }

    int queries;
    fin >> queries;
    int lg = getLg(n);

    for (int i = 0; i < queries; ++i) {
        int type, x;
        fin >> type >> x;
        if (type == 0)
            fout << firstTask(x, lg, n, a) << '\n';
        else if (type == 1)
            fout << secondTask(x, lg, n, a) << '\n';
        else if (type == 2)
            fout << thirdTask(x, lg, n, a) << '\n';
    }
    return 0;
}