#include <fstream>
#include <iostream>

using namespace std;


ifstream f("cautbin.in");
ofstream g("cautbin.out");

int v[100001];

int CautareBinara0 (int st, int dr, int Elment)
{
    int mijloc;

    while (st <= dr)
    {
        mijloc = (st + dr) / 2;
        if (v[mijloc] <= Elment)
            st = mijloc + 1;
        else
            dr = mijloc - 1;
    }
    mijloc = (st + dr) / 2;

    if (v[mijloc] > Elment) mijloc --;
    if (v[mijloc] == Elment)
        return mijloc;
    return -1;
}

int CautareBinara1 (int st, int dr, int Elment)
{
    int m, n = dr;

    while (st < dr){
        m = (st + dr) / 2;
        if (v[m] <= Elment)
            st = m + 1;
        else
            dr = m;
    }

    m = (st + dr) / 2;
    if (v[m] > Elment)
       -- m;
    return m;
}

int CautareBinara2 (int st, int dr, int Elment)
{
    int m;

    while (st < dr) {
        m = (st + dr) / 2;
        if (v[m] < Elment)
            st = m + 1;
        else
            dr = m;
    }

    m = (st + dr) / 2;
    if (v[m] < Elment)
       ++ m;
    return m;
}

int main ()
{
    int i, n, m, tip, val;

    f >> n;

    for (i = 1; i <= n; ++ i)
        f >> v[i];

    f >> m;

   for (int j=1; j<=m; ++j)
    {
          f >> tip >> val;

          if (tip == 0)
             g << (CautareBinara0(1, n, val)) << "\n";

          if (tip == 1)
             g << (CautareBinara1(1, n, val)) << "\n";

          if (tip == 2)
             g << (CautareBinara2(1, n, val)) << "\n";
    }
    return 0;
}