#include <bits/stdc++.h>

using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int bsearch0(int v[], int x, int n)
{
    int st, dr, mij;
    st = 1;
    dr = n;
    while (st <= dr)
    {
        mij = (st + dr) / 2;
        if (x == v[mij])
        {
            st = -1;
            break;
        }
        else
            if (x <=v [mij])
                dr = mij - 1;
            else
                st = mij + 1;
    }
    if (st == -1)
    {
    while (x == v[mij])
                mij++;
        return mij-1;
    }
    return -1;
}
int bsearch1(int v[], int x, int n)
{
    int st, dr, mij;
    st = 1;
    dr = n;
    while (st <= dr)
    {
        mij = (st + dr) / 2;
        if (v[mij] <= x)
        {
            st = -1;
            break;
        }
        else
            if (x <= v[mij])
                dr = mij - 1;
            else
                st = mij + 1;
    }
    if (st == -1)
    {
        while (v[mij] <= x)
                mij++;
        return mij - 1;
    }
    return -1;
}
int bsearch2(int v[],int x,int n)
{
    int st, dr, mij;
    st = 1;
    dr = n;
    while (st <= dr)
    {
        mij = (st + dr) / 2;
        if (x <= v[mij])
        {
            break;
            st = -1;
        }
        else
            if (x <= v[mij])
                dr = mij - 1;
            else
                st = mij + 1;
    }
    if (st == -1)
    {
        while (x <= v[mij])
                mij--;
        return mij + 1;
    }
    return -1;
}
int main()
{
    int n, m, i, y, x, v[100015];
    f >> n;
    for (i = 1;i <= n; i++)
        f >> v[i];
    f >> m;
    for (i = 1;i <= m; i++)
    {
        f >> y;
        if (y == 0)
        {
            f >> x;
            g << bsearch0(v, x, n) << endl;
        }
        else
            if (y == 1)
            {
                f >> x;
                g << bsearch1(v, x, n) << endl;
            }
            else
                if (y == 2)
                {
                    f >> x;
                    g << bsearch2(v, x, n) << endl;
                }
    }
    return 0;
}