#include <fstream>

using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

const int NMAX = 1e5 + 1;

int n, m;
int st = 1;
int a[NMAX];

inline void read() {
    fin >> n;
    for (int i = 1; i <= n; ++i)
        fin >> a[i];
    fin >> m;
    while ((st << 1) <= n)
        st <<= 1;
}

inline int lowerBoundSearch(int val) {
    int step = st;
    int ans;
    for (ans = 1; step; step >>= 1)
        if (ans + step <= n && a[ans + step] <= val)
            ans += step;
    return ans;
}

inline int upperBoundSearch(int val) {
    int step = st;
    int ans;
    for (ans = n; step; step >>= 1)
        if (ans - step >= 1 && a[ans - step] >= val)
            ans -= step;
    return ans;
}

inline void solveQueries() {
    int op, val;
    int ans;
    while (m--) {
        fin >> op >> val;
        if (op == 0) {
            ans = lowerBoundSearch(val);
            if (a[ans] != val)
                fout << -1 << '\n';
            else
                fout << ans << '\n';
        }
        else if (op == 1) {
            ans = lowerBoundSearch(val);
            fout << ans << '\n';
        }
        else {
            ans = upperBoundSearch(val);
            fout << ans << '\n';
        }
    }
}

int main()
{
    read();
    solveQueries();

    fin.close();
    fout.close();
    return 0;
}