#include <fstream>

using namespace std;

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

int n,v[100001],q,x,t;

int c_bin_tip_0(int nr)
{
    int st=1;
    int dr=n;
    int mid=0;
    int poz=-1;

    while(st<=dr)
    {
        mid=(st+dr)/2;
        if(v[mid]<=nr)
        {
            if(v[mid]==nr)
                poz=mid;
            st=mid+1;
        }
        else
            dr=mid-1;
    }
    return poz;
}

int c_bin_tip_1(int nr)
{
    int st=1;
    int dr=n;
    int mid=0;
    int poz=-1;

    while(st<=dr)
    {
        mid=(st+dr)/2;
        if(v[mid]<=nr)
        {
            st=mid+1;
        }
        else
            dr=mid-1;
    }
    return dr;
}
int c_bin_tip_2(int nr)
{
    int st=1;
    int dr=n;
    int mid=0;
    int poz=-1;

    while(st<=dr)
    {
        mid=(st+dr)/2;
        if(v[mid]<nr)
        {
            st=mid+1;
        }
        else
        {
            poz=mid;
            dr=mid-1;
        }

    }
    return poz;
}


int main()
{
    fin>>n;
    for(int i=1;i<=n;i++)
    {
        fin>>v[i];
    }
        fin>>q;
        for(int i=1;i<=q;i++)
        {
            fin>>t>>x;
            if(t==0)
            {
                fout<<c_bin_tip_0(x)<<"\n";
            }
            else if (t==1)
            {
                fout<<c_bin_tip_1(x)<<"\n";
            }
            else if(t==2)
            {
                fout<<c_bin_tip_2(x)<<"\n";
            }

        }

}