#include <fstream>

using namespace std;

int v[100000],n,m;

int c1(int x)
{
    int i,p,u,mij;
    p=1;
    u=n;
    while (p<=u)
    {
        mij=(p+u)/2;
        if (x>=v[mij])
            p=mij+1;
        else
            u=mij-1;
    }
    mij=(p+u)/2;
    if (v[mij]>x)
        mij--;
    if (v[mij]==x)
        return mij;
    return -1;
}

int c2(int x)
{
    int i,p,u,mij;
    p=1;
    u=n;
    while (p<u)
    {
        mij=(p+u)/2;
        if (x>=v[mij])
            p=mij+1;
        else
            u=mij;
    }
    mij=(u+p)/2;
    if (v[mij]>x)
        mij--;
    return mij;
}

int c3(int x)
{
    int i,p,u,mij;
    p=1;
    u=n;
    while (p<u)
    {
        mij=(p+u)/2;
        if (x>v[mij])
            p=mij+1;
        else
            u=mij;
    }
    mij=(u+p)/2;
    if (v[mij]<x)
        m++;
    return mij;
}

int main()
{
    int i,c,x;
    bool sem;
    ifstream f("cautbin.in");
    ofstream g("cautbin.out");
    f>>n;
    for (i=1;i<=n;i++)
        f>>v[i];
    f>>m;
    for (i=0;i<m;i++)
        {
            f>>c>>x;
            switch (c)
            {
                case 0:
                    g<<c1(x);
                    break;
                case 1:
                    g<<c2(x);
                    break;
                case 2:
                    g<<c3(x);
                    break;
            }
            g<<'\n';
        }
    return 0;
}