#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

int main()
{
    vector<int> v;
    v.reserve(100005);

    int n;
    fin >> n;
    for (int i = 0; i < n; i++)
    {
        int x;
        fin >> x;
        v.push_back(x);
    }

    int k;
    fin >> k;
    for (int i = 0; i < k; i++)
    {
        int c, x;
        fin >> c >> x;

        if (c == 0)
        {
            int ind = upper_bound(v.begin(), v.end(), x) - v.begin();

            if (v[ind - 1] == x) fout << ind << '\n';
            else fout << -1 << '\n';
        }
        else if (c == 1)
        {
            int ind = upper_bound(v.begin(), v.end(), x) - v.begin();
            fout << ind << '\n';
        }
        else
        {
            int ind = lower_bound(v.begin(), v.end(), x) - v.begin();

            if (v[ind] == x) fout << ind + 1 << '\n';
            else fout << ind << '\n';
        }
    }

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