#include <fstream>

	
int bsearch2 (int *v, int start, int end, int sought) {
    int mid;
 
    while (start < end) {
        mid = (start + end) / 2;
        if (v[mid] < sought)
            start = mid + 1;
        else
            end = mid;
    }
    
    mid = (start + end) / 2;
    if (v[mid] < sought)
       mid++;
    return mid + 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;
}