#include <fstream>

std::ifstream in ("cautbin.in");
std::ofstream out("cautbin.out");

int binery0(int val, int n, int a[]){
    int lower = 0, upper = n - 1, nr = -1, middle;
    while (lower <= upper){
        middle = lower +(upper - lower)/2;
        if (a[middle] == val){
            nr = std::max(middle + 1,nr);
            lower = middle + 1;
        } else if (a[middle] < val){
            lower = middle + 1;
        }
        else {
            upper = middle - 1;
        }
    }
    return nr;
}

int binery1(int val, int n, int a[]){
    int lower = 0, upper = n - 1, nr = -1, middle;
    while (lower <= upper){
        middle = lower +(upper - lower)/2;
        if (a[middle] <= val){
            nr = std::max(middle + 1,nr);
            lower = middle + 1;
        } else if (a[middle] < val){
            lower = middle + 1;
        }
        else {
            upper = middle - 1;
        }
    }
    return nr;
}

int binery2(int val, int n, int a[]){
    int lower = 0, upper = n - 1, nr = n, middle;
    while (lower <= upper){
        middle = lower +(upper - lower)/2;
        if (a[middle] >= val){
            nr = std::min(middle + 1,nr);
            upper = middle - 1;
        } else if (a[middle] < val){
            lower = middle + 1;
        }
        else {
            upper = middle - 1;
        }
    }
    return nr;
}

int main()
{
    int n;
    in >> n;
    int a[n];
    for (int i = 0; i < n; i ++)
        in >> a[i];
    int query;
    in >> query;
    while (query--){
        int op, val;
        in >> op >> val;
        switch (op){
            case 0:
                out << binery0(val,n,a) << "\n";
                break;
            case 1:
                out << binery1(val,n,a) << "\n";
                break;
            case 2:
                out << binery2(val,n,a) << "\n";
                continue;
        }
    }
    in.close();
    out.close();
    return 0;
}