#include <fstream>

using namespace std;

ifstream f("cautbin.in");
ofstream g("cautbin.out");

#define NMAX 100005

int n, m, v[NMAX], put = 1;

void citire() {
    f >> n;
    for (int i = 1; i <= n; ++i)
        f >> v[i];
    while (put < n)
        put <<= 1;
}

int cautare_binara0(int x) {
    int i = 0;
    for (int l = put; l > 0; l >>= 1)
        if (i + l <= n && x >= v[i + l])
            i += l;
    if (v[i] == x)
        return i;
    return -1;
}

int cautare_binara1(int x) {
    int i = 0;
    for (int l = put; l > 0; l >>= 1)
        if (i + l <= n && x >= v[i + l])
            i += l;
    return i;
}

int cautare_binara2(int x) {
    int i = 0;
    for (int l = put; l > 0; l >>= 1)
        if (i + l <= n && x > v[i + l])
            i += l;
    return i + 1;
}

void rezolvare() {
    f >> m;
    int tip, x;
    for (int i = 1; i <= m; ++i) {
        f >> tip >> x;
        if (tip == 0)
            g << cautare_binara0(x) << '\n';
        else if (tip == 1)
            g << cautare_binara1(x) << '\n';
        else
            g << cautare_binara2(x) << '\n';
    }
}

int main() {
    citire();
    rezolvare();
    return 0;
}