#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5;
const int MAXM = 1e5;

int cb(int nr, vector<int> v)
{
    int acc = 0, pow2 = 1 << 16;
    while (pow2)
    {
        int index = pow2 + acc;
        if (index < v.size() && v[index] < nr)
            acc = index;
        pow2 >>= 1;
    }

    return acc;
}

int main()
{
    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);

    int n, m;
    cin >> n;
    vector<int> v(n + 1);

    v[0] = 0;
    for (int i = 1; i <= n; ++i)
        cin >> v[i];

    cin >> m;

    int op, x;
    int index;

    while (m--)
    {
        cin >> op >> x;

        if (op == 0)
        {
            index = cb(x + 1, v);
            if (index == 0 || v[index] != x)
                cout << -1 << '\n';
            else
                cout << index << '\n';
        }
        if (op == 1)
        {
            index = cb(x + 1, v);
            cout << index << '\n';
        }
        if (op == 2)
        {
            index = cb(x, v);
            cout << index + 1 << '\n';
        }
    }

    return 0;
}