#include <fstream>

using namespace std;

const int N = 100001;
const int L = 16;
int v[N], n;

int caut0(int x) {
    int r = 0, pas = 1 << L;
    while (pas != 0) {
        if (r + pas <= n && v[r + pas] <= x) {
            r += pas;
        }
        pas /= 2;
    }
    if (v[r] != x) {
        r = -1;
    }
    return r;
}

int caut1(int x) {
    int r = 0, pas = 1 << L;
    while (pas != 0) {
        if (r + pas <= n && v[r + pas] <= x) {
            r += pas;
        }
        pas /= 2;
    }
    return r;
}

int caut2(int x) {
    int r = 0, pas = 1 << L;
    while (pas != 0) {
        if (r + pas <= n && v[r + pas] < x) {
            r += pas;
        }
        pas /= 2;
    }
    r++;
    return r;
}

int main() {
    ifstream in("cautbin.in");
    ofstream out("cautbin.out");
    in >> n;
    for (int  i = 1; i <= n; i++) {
        in >> v[i];
    }
    int m, tip, val;
    in >> m;
    for (int i = 0; i < m; i++) {
        in >> tip >> val;
        if (tip == 0) {
            out << caut0(val) << "\n";
        } else if (tip == 1) {
            out << caut1(val) << "\n";
        } else {
            out << caut2(val) << "\n";
        }
    }
    in.close();
    out.close();
    return 0;
}