#include <iostream>
#include <fstream>

using namespace std;

ifstream f("cautbin.in");
ofstream g("cautbin.out");
const int NMAX = 100001;
int v[NMAX];

int main()
{
    int N;
    f >> N;
    for (int i = 1; i <= N; i++)
    {
        f >> v[i];
    }
    int Q;
    f >> Q;
    while (Q--)
    {
        int tip, x;
        f >> tip >> x;
        if (tip == 0)
        {
            int st = 1, dr = N, poz = -1;
            while (st <= dr)
            {
                int mij = (st + dr) / 2;
                if (v[mij] == x)
                {
                    poz = mij;
                    st = mij + 1; /// caut un element mai bun
                }
                else if (v[mij] < x) /// am nimerit cu mijlocul in stanga lui x
                {
                    st = mij + 1;/// mut cautarea in dreapta
                }
                else
                {
                    /// trebuie sa cautam un element mai mic, deci mut cautarea in stanga
                    dr = mij - 1;
                }
            }
            g << poz << '\n';
        }
        else if (tip == 1)
        {
            int st = 1, dr = N, poz = 0;
            while (st <= dr)
            {
                int mij = (st + dr) / 2;
                if (v[mij] > x)
                {
                    dr = mij - 1;
                }
                else ///v[mij] <= x, deci fix ce imi trebuie mie
                {
                    poz = mij; // il tin minte ca potential raspuns
                    st = mij + 1; /// caut un raspuns mai bun
                }
            }
            g << poz << '\n';
        }
        else if (tip == 2)
        {
            int st = 1, dr = N, poz;
            while (st <= dr)
            {
                int mij = (st + dr) / 2;
                if (v[mij] >= x)
                {
                    /// am gasit un element cu valoare mai mare sau egala
                    /// il tin minte si caut un element mai mic
                    poz = mij;
                    dr = mij - 1;
                }
                else /// daca v[mij] < x
                {
                    st = mij + 1;
                }
            }
            g << poz << '\n';
        }

    }
    return 0;
}