#include <iostream>
#include <fstream>

	
int bsearch2 (int *v, int p, int u, int key) {
    int m;
 
    while (p < u) {
        m = (p + u) / 2;
        if (v[m] < key)
            p = m + 1;
        else
            u = m;
    }
    
    m = (p + u) / 2;
    if (v[m] < key)
       ++ m;
    return m+1;
}

int binary(int* v, int size, int sought, int command) {


    int i = 0, step;
    if (command == 0 || command == 1) {
        for (step = 1; step < size; step <<= 1);
        int prev = step - 1;
        do {
            if (i + step < size && v[i + step] <= sought) {
                i += step;
            }
            prev = i + step;
            step >>= 1;
        } while (prev > (step + i));

        if (command == 0 && prev < size && v[prev] != sought)
            return -1;

        if (command == 1 && prev < size && v[prev] > sought)
            return -1;
        return prev + 1;
    }

    if (command == 2) {
        return bsearch2(v, 0, size, sought);
    }

    return -1;
}

int main() {
    std::ifstream f("cautbin.in");
    std::ofstream g("cautbin.out");
    int N;
    f >> N;
    //std::cout << N << "\n";
    int* a = new int[N];
    for (int i = 0; i < N; ++i) {
        f >> a[i];
    }

    int c;
    int command, s;
    f >> c;
    for (int i = 0; i < c; ++i) {
        f >> command >> s;
        g << binary(a, N, s, command) << "\n";
        //std::cout << i << "\n";
    }
    delete[] a;
}