#include <fstream>
#define NMAX 100005
using namespace std;
ifstream fin ("cautbin.in");
ofstream fout ("cautbin.out");

int v[NMAX], n, m;

int querry0(int val, int left, int right) {
    int m = (left + right)/2;
    if(left == right) {
        if(val == v[left])
            return left;
        else if(val == v[left - 1])
                return left - 1;
        else return -1;
    }
    if(val >= v[m]) {
        return querry0(val, m+1, right);
    }
    if(val < v[m]) {
        return querry0(val, left, m-1);
    }
}

int querry1(int val, int left, int right) {
    int m = (left + right)/2;
    if(left == right) {
        if(v[left] > val)
            return left - 1;
        return left;
    }
    if(val >= v[m]) {
        return querry1(val, m+1, right);
    }
    if(val < v[m]) {
        return querry1(val, left, m-1);
    }
}

int querry2(int val, int left, int right) {
    int m = (left + right)/2;
    if(left == right) {
        if(v[left] < val)
            return left + 1;
        return left;
    }
    if(val > v[m]) {
        return querry2(val, m+1, right);
    }
    if(val <= v[m]) {
        return querry2(val, left, m-1);
    }
}

int main() {

    int t, x;

    fin >> n;
    for(int i=1; i<=n; i++)
        fin >> v[i];
    fin >> m;
    for(int i=1; i<=m; i++) {
        fin >> t;
        if(t == 0) fin >> x, fout << querry0(x, 1, n) << endl;
        if(t == 1) fin >> x, fout << querry1(x, 1, n) << endl;
        if(t == 2) fin >> x, fout << querry2(x, 1, n) << endl;
    }

    return 0;
}