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

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

    int n;
    fin >> n;

    vector<int> v(n);
    for (int i = 0; i < n; i++)
        fin >> v[i];

    int q;
    fin >> q;

    for (int i = 0; i < q; i++) {
        int tip, val;
        fin >> tip >> val;

        if (tip == 0) {
            auto it = upper_bound(v.begin(), v.end(), val);
            int pos = it - v.begin() - 1;

            if (pos >= 0 && v[pos] == val)
                fout << pos+1 << "\n";
            else
                fout << "-1\n";
        }
        else if (tip == 1) {
            auto it = upper_bound(v.begin(), v.end(), val);
            int pos = it - v.begin() - 1;
            fout << pos+1 << "\n";
        }
        else { // 2
            auto it = lower_bound(v.begin(), v.end(), val);
            int pos = it - v.begin();
            fout << pos+1 << "\n";
        }
    }

    return 0;
}