#include <bits/stdc++.h>
#define DAU  ios_base::sync_with_stdio(false); fin.tie(0); fout.tie(0);
#define PLEC fin.close(); fout.close(); return 0;
using namespace std;
const string problem("cautbin");
ifstream fin(problem + ".in");
ofstream fout(problem + ".out");
int n, q, op, x, poz;
vector<int> v;
int main() {
    DAU
    fin >> n;
    v = vector<int>(n + 1);
    for (int i = 1; i <= n; ++i)
        fin >> v[i];
    fin >> q;
    while (q--) {
        fin >> op >> x;
        if (op == 0) {
            poz = upper_bound(v.begin(), v.end(), x) - v.begin() - 1;
            if (v[poz] != x)
                fout << "-1\n";
            else fout << poz << '\n';
        }
        else if (op == 1) {
            poz = upper_bound(v.begin(), v.end(), x) - v.begin() - 1;
            fout << poz << '\n';
        }
        else {
            poz = lower_bound(v.begin(), v.end(), x) - v.begin();
            fout << poz << '\n';
        }

    }
    PLEC
}