#include <fstream>

using namespace std;

ifstream f("cautbin.in");
ofstream g("cautbin.out");
int v[100010],n,nr;
int tip0(int n,int nr)
{
    int p=1,m;
    while (p<=n)
    {
        m=(p+n)/2;
        if (v[m]<=nr)
        {
            p=m+1;
        }
        else
        {
           n=m-1;
        }

    }
    m=(p+n)/2;
    if (v[m]>nr)m--;
    if (v[m]==nr)
    {
        return m;
    }
    return -1;
}
int tip1(int n,int nr)
{
     int p=1,m;
    while (p<n)
    {
        m=(p+n)/2;
        if (v[m]<=nr)
        {
            p=m+1;
        }
        else
        {
           n=m;
        }

    }
    m=(p+n)/2;
    if (v[m]>nr)m--;
    return m;
}
int tip2(int n,int nr)
{
         int p=1,m;
    while (p<n)
    {
        m=(p+n)/2;
        if (v[m]<nr)
        {
            p=m+1;
        }
        else{n=m;}

    }
    m=(p+n)/2;
    if (v[m]<nr)++m;
    return m;
}
int main()
{int n,i,m,t,nr;
    f>>n;
    for (i=1;i<=n;i++)
    {
        f>>v[i];
    }
    f>>m;
    for (i=1;i<=m;i++)
    {
        f>>t>>nr;
        if (t==0)
        {
            g<<tip0(n,nr)<<'\n';
        }
        else
        if (t==1)
        {
            g<<tip1(n,nr)<<'\n';
        }
        else
        if (t==2)
        {
            g<<tip2(n,nr)<<'\n';
        }
    }
    return 0;
}