#include <bits/stdc++.h>

using namespace std;

int N, M, v[100005];

int cb(int op, int x) {
    int s = 1, d = N, m, r = -1;
    if(op == 0) {
        while(s <= d) {
            m = (s + d) / 2;
            if(v[m] == x)r = max(r, m);
            (v[m] <= x) ? s = m + 1 : d = m - 1;
        }
        return r;
    }
    if(op == 1) {
        while(s <= d) {
            m = (s + d) / 2;
            (v[m] <= x) ? r = m, s = m + 1 : d = m - 1;
        }
        return r;
    }
    if(op == 2) {
        while(s <= d) {
            m = (s + d) / 2;
            (v[m] >= x) ? d = m - 1, r = m : s = m + 1;
        }
        return r;
    }
}

int main() {
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");
    fin >> N;
    for(int i = 1; i <= N; ++i)
         fin >> v[i];
    fin >> M;
    int op, x;
    while(M--) {
        fin >> op >> x;
        fout << cb(op, x) << "\n";
    }
}