#include <fstream>

using namespace std;

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

int a[100001],n;

int intrebare0(int x)
{

    int prima=1,ultima=n,mijloc,retine=0;

    while(prima<=ultima)
    {
        mijloc=(prima+ultima)/2;

        if(a[mijloc]<=x)
            prima=mijloc+1;
        else
            ultima=mijloc-1;

    }
    if(a[ultima]==x)
        return ultima ;
    else
        return -1;
}

int intrebare1(int x)
{
    int prima=1,ultima=n,mijloc,retine=0;

    while(prima<=ultima)
    {
        mijloc=(prima+ultima)/2;

        if(a[mijloc]<=x)
            prima=mijloc+1;
        else
            ultima=mijloc-1;

    }
        return ultima;
}

int intrebare2(int x)
{

    int prima=1,ultima=n,mijloc,retine=0;

    while(prima<=ultima)
    {
        mijloc=(prima+ultima)/2;

        if(a[mijloc]>=x)
            ultima=mijloc-1;
        else
            prima=mijloc+1;

    }
        return prima;
}


int main()
{
    int i,m,nr,x;
    in>>n;

    for(i=1; i<=n; i++)
        in>>a[i];

    in>>m;

    for(i=1;i<=m;i++)
    {
        in>>nr;
        in>>x;
        if(nr==0)
            out<<intrebare0(x)<<'\n';
        if(nr==1)
            out<<intrebare1(x)<<'\n';
        if(nr==2)
            out<<intrebare2(x)<<'\n';
    }

    return 0;
}