#include <fstream>
using namespace std;

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

        int N[100000], n, M;
        int inst;
        int nr;
        fin >> n;
        for (int i = 0; i < n; ++i)
            fin >> N[i];
        fin >> M;

        int mijl, numero, m;
        int l, r;
        while (M)
        {
            fin >> inst >> nr;

            if (inst == 0)
            {
                do{
                     for(int i = 0; i < n; ++i)
                    {
                    r = N[0];
                    l = N[n - 1];
                    m = (r + l) / 2;
                    if (N[m] == nr)
                        fout << m << '\n';
                    if (nr > N[m])
                        r = m + 1;
                    if (nr < N[m])
                        l = m - 1;
                    }
                } while (r < l);

            }

                if (inst == 1)
                {
                    do{
                     for(int i = 0; i < n; ++i)
                    {
                        r = N[0];
                        l = N[n - 1];
                        m = (r + l) / 2;
                        if (N[m] <= nr)
                            numero = m;
                        if (nr > N[m])
                            r = m + 1;
                        if (nr < N[m])
                            l = m - 1;
                    }
                    } while (r < l);
                    fout << numero << '\n';
                }

                if (inst == 2)
                {
                    do{
                     for(int i = 0; i < n; ++i)
                        {
                            r = N[0];
                            l = N[n - 1];
                            m = (r + l) / 2;
                            if (N[m] >= nr)
                                numero = m;
                            if (nr > N[m])
                                r = m + 1;
                            if (nr < N[m])
                                l = m - 1;
                        }
                        } while (r < l);
                        fout << numero << '\n';
                }

                --M;
            }

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