#include <fstream>

using namespace std;

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

int v[100002],n,m;

/// cea mai mare pozitie pe care se afla un element cu valoarea x sau -1 daca aceasta valoare nu se gaseste in sir
int binara0(int x)
{
    int hi,lo,mi;
    hi=n-1;
    lo=0;

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

    if (v[mi]>x)
        mi--;
    if (v[mi]==x)
        return mi+1;
    return -1;
}

/// cea mai mare pozitie pe care se afla un element cu valoarea mai mica sau egala cu x in sir
int binara1(int x)
{
    int hi,lo,mi;
    hi=n-1;
    lo=0;

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

    if (v[mi]==x)
        mi--;

    return mi;
}

/// cea mai mica pozitie pe care se afla un element cu valoarea mai mare sau egala cu x in sir
int binara2(int x)
{
    int hi,lo,mi;
    hi=n-1;
    lo=0;

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

    if (v[mi]==x)
        mi++;

    return mi;
}

int main()
{
    fin >> n;

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

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

        switch(tip)
        {
            case 0: {fout << binara0(x) << "\n";break;}
            case 1: {fout << binara1(x) << "\n";break;}
            case 2: {fout << binara2(x) << "\n";break;}
        }
    }

    return 0;
}