#include <fstream>

using namespace std;
int tip,x,m,n,a[100001];
int cb0(int  val)
{
       int st=1; int dr=n; int mij=(st+dr)/2;
       while (st<=dr)
       {
           mij=(st+dr)/2;
           if (a[mij]<=val) st=mij+1;
           else dr=mij-1;
       }
       if (a[mij]>val) mij--;
       if (a[mij]==val) return mij;
       else return -1;
}

int cb1(int val)
{
    int st=1;int dr=n;int mij=(st+dr)/2;
    while (st<dr)
    {
        mij=(st+dr)/2;
        if (a[mij]<=val) st=mij+1;
        else dr=mij;
    }
    mij=(st+dr)/2;
    if (a[mij]>val) mij--;
    return mij;
}

int cb2(int val)
{
    int st=1;int dr=n;int mij=(st+dr)/2;
    while (st<dr)
    {
        mij=(st+dr)/2;
        if (a[mij]<val) st=mij+1;
        else dr=mij;
    }
    if (a[mij]<val) mij++;
    return mij;
}
int main()
{
    ifstream f("cautbin.in");
    ofstream g("cautbin.out");
    f>>n;int poz=0; int i=0;
    for (i=1;i<=n;i++) f>>a[i];
    f>>m;
    for (i=1;i<=m;i++)
    {
        f>>tip>>x;
        if (tip==0)
        {
            poz=cb0(x);
             g<<poz<<'\n';
        }
        if (tip==1)
        {
            poz=cb1(x);
            g<<poz<<'\n';
        }
        if (tip==2)
        {
            poz=cb2(x);
            g<<poz<<'\n';
        }
    }
    f.close();
    g.close();
    return 0;
}