#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5;

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

int v[MAXN + 5], st, dr, n, poz, mij;

int bin0(int x)
{
    st = 1;
    dr = n;
    poz = -1;

    while (st <= dr)
    {
        mij = (st + dr) >> 1;
        if (v[mij] == x)
        {
            poz = mij;
            st = mij + 1;
        }
        else if (v[mij] > x)
        {
            dr = mij - 1;
        }
        else
        {
            st = mij + 1;
        }
    }

    return poz;
}

int bin1(int x)
{
    st = 1;
    dr = n;

    while (st <= dr)
    {
        mij = (st + dr) >> 1;
        if (v[mij] <= x)
        {
            poz = mij;
            st = mij + 1;
        }
        else
        {
            dr = mij - 1;
        }
    }

    return poz;
}

int bin2(int x)
{
    st = 1;
    dr = n;

    while (st <= dr)
    {
        mij = (st + dr) >> 1;
        if (v[mij] >= x)
        {
            poz = mij;
            dr = mij - 1;
        }
        else
        {
            st = mij + 1;
        }
    }

    return poz;
}

int main()
{
    int i, t, tip, x;

    fin >> n;

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

    fin >> t;

    while (t--)
    {
        fin >> tip >> x;
        if (!tip)
            fout << bin0(x) << '\n';
        else if (tip == 1)
            fout << bin1(x) << '\n';
        else
            fout << bin2(x) << '\n';
    }

    return 0;
}