#include <iostream>
#include <fstream>

using namespace std;

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

int n, m;
long long sir[100001];

int cautare_binara_la_dreapta(int nr) {
    int st = 1;
    int dr = n;
    int m = (st + dr) / 2;
    int sol = -1;

    while (st <= dr) {
        if (sir[m] == nr) {
            sol = m;
            if (sir[m + 1] == nr && m + 1 <= n) {
                st = m + 1;
                sol = m + 1;
            } else {
                return sol;
            }
        } else if (nr > sir[m]) {
            st = m + 1;
        } else {
            dr = m - 1;
        }

         m = (st + dr) / 2;

    }

    return sol;
}

int cautare_binara_la_stanga(int nr) {
    int st = 1;
    int dr = n;
    int m = (st + dr) / 2;
    int sol = -1;

    while (st <= dr) {
        if (sir[m] == nr) {
            sol = m;
            if (sir[m - 1] == nr && m - 1 >= 1) {
                dr = m - 1;
                sol = m - 1;
            } else {
                return sol;
            }
        } else if (nr > sir[m]) {
            st = m + 1;
        } else {
            dr = m - 1;
        }

        m = (st + dr) / 2;

    }

    return sol;
}

int main() {
    fin >> n;

    for (int i = 1; i <= n; ++i) {
        fin >> sir[i];
    }

    fin >> m;

    for (int i = 1; i <= m; ++i) {
        int t, x;
        fin >> t >> x;

        if (t == 0) {
            fout << cautare_binara_la_dreapta(x) << "\n";
        } else if (t == 1) {
            int r = cautare_binara_la_dreapta(x);

            if (r == -1) {
                int stop = 0;

                while (stop == 0) {
                    if (x - 1 >= sir[1] && r == -1) {
                        r = cautare_binara_la_dreapta(x-1);
                    } else {
                        stop = 1;
                    }
                }

                fout << r << "\n";
            } else {
                fout << r << "\n";
            }
        } else {
            int r = cautare_binara_la_stanga(x);

            if (r == -1) {
                int stop = 0;

                while (stop == 0) {
                    if (x + 1 <= sir[n] && r == -1) {
                        r = cautare_binara_la_stanga(x+1);
                        ++x;
                    } else {
                        stop = 1;
                    }
                }

                fout << r << "\n";
            } else {
                fout << r << "\n";
            }
        }

    }

    return 0;
}