# include <fstream>
std::ifstream f("cautbin.in");
std::ofstream g("cautbin.out");
long i,n,nr,mi,m,cs,cd;
long v[100000];
short y;

int main()
{
    f>>n;
    for (i=1;i<=n;i++) f>>v[i];
    f>>m;
    for (i=1;i<=m;i++)
    {
        f>>y>>nr;
        cs=1;
        cd=n;
        mi=(cs+cd)/2;
        while ((v[mi]!=nr) && (cd-cs>1))
        {
            if (v[mi]<nr) cs=mi; else cd=mi;
            mi=(cs+cd)/2;
        }

        if (y<2)
        {
            while (v[mi+1]==nr) mi++;
            if (v[mi]==nr) g<<mi<<"\n";
            else {
                   if (y==0) g<<-1<<"\n";
                   if (y==1) {if (v[mi+1]<nr) mi++; g<<mi<<"\n";}
                 }

        }
        else
        {
            while (v[mi-1]==nr) mi--;
            if (v[mi-1]>=nr) mi--;
            if (v[mi]<nr) mi++;
            g<<mi<<"\n";
        }
    }
}