#include <fstream>

using namespace std;

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

int v[100002];

// cea mai mare pozitie pe care se afla un element cu valoarea x sau -1 daca aceasta valoare nu se gaseste in sir

int b0(int x, int lo, int hi)
{
    int mi;

    while (lo<hi)
    {
        mi=lo+(hi-lo+1)/2;
        if (v[mi]<=x)
            lo=mi;
        else
            hi=mi-1;
    }

    if (v[lo]==x)
        return lo;
    return -1;
}

// cea mai mare pozitie pe care se afla un element cu valoarea mai mica sau egala cu x in sir

int b1(int x, int lo, int hi)
{
    int mi;

    while (lo<hi)
    {
        mi=lo+(hi-lo+1)/2;
        if (v[mi]<=x)
            lo=mi;
        else
            hi=mi-1;
    }
    return lo;
}

// cea mai mica pozitie pe care se afla un element cu valoarea mai mare sau egala cu x in sir

int b2(int x,int lo, int hi)
{
    int mi;

    while (lo<hi)
    {
        mi=lo+(hi-lo)/2;
        if (v[mi]<x)
            lo=mi+1;
        else
            hi=mi;
    }
    return hi;
}

int main()
{
    int n;
    fin >> n;

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

    int x,m;
    char tip;
    fin >> m;
    while (m--)
    {
        fin >> tip >> x;

        if (tip=='0')
        {
            fout << b0(x,1,n) << "\n";
            continue;
        }
        if (tip=='1')
        {
            fout << b1(x,1,n) << "\n";
            continue;
        }
        if (tip=='2')
        {
            fout << b2(x,1,n) << "\n";
            continue;
        }
    }

    return 0;
}