using namespace std;



#define fisier "cautbin"

#ifdef fisier
    #include <fstream>
    ifstream in(fisier ".in");
    ofstream out(fisier ".out");
#else
    #include <iostream>
    #define in cin
    #define out cout
#endif



int n, v[100000];



inline bool mai_mic(bool sau_egal, int a, int b) {

    return sau_egal?
        (a <= b):
        (a < b);

}



int cb(int val, bool sau_egal, bool rt_i) {

    int i = 0, j = n - 1, mij;

    while (i <= j) {

        //out << "cb(" << i << ", " << j << ")\n";

        mij = (i + j) / 2;

        if (mai_mic(sau_egal, v[mij], val)) {

            i = mij + 1;

        } else {

            j = mij - 1;

        }

    }

    //out << "cb(" << i << ", " << j << ")\n";

    if (rt_i)
        return i;

    return j;

}



int main() {

    int m, val, tip, rez;



    in >> n;

    for (rez = 0; rez < n; rez++) {

        in >> v[rez];

    }



    in >> m;

    while (m--) {

        in >> tip >> val;

        switch (tip) {

            case 0:

                rez = cb(val, true, false);

                if (rez != -1 && v[rez] != val) {

                    rez = -2;

                }

                break;


            case 1:

                rez = cb(val, true, false);

                break;


            case 2:

                rez = cb(val, false, true);

                break;

        }

        out << rez + 1 << '\n';

    }

}





//