#include <fstream>

using namespace std;

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

long long v[100001],k ;

int main()
{
    long long p,u,i,n,mij,ok,a,m,max=0 ;
    f>>n ;
    for(i=1;i<=n;i++)
        f>>v[i] ;
    f>>m ;

for(i=1;i<=m;i++)
{
    f>>a>>k ;
    if(a==0)
    {
        p=1 ;
        u=n ;
        ok=0 ;

        while(p<u)
        {
            mij=p+(u-p)/2 ;
            if(v[mij]==k)
            {
                while(v[mij]==k)
                    mij++ ;
                g<<mij-1<<"\n" ;
                ok=1 ;
                break ;
            }
            else
            {
                if(v[mij]<k)
                    p=mij+1 ;
                if(v[mij]>k)
                    u=mij-1 ;
            }

        }
        if(ok==0)
            g<<"-1\n" ;


    }
    if(a==1)
    {
        p=1 ;
        u=n ;
        ok=0 ;

        while(p<u)
        {
            mij=p+(u-p)/2 ;
            if(v[mij==k])
            {
                while(v[mij]==k)
                    mij++ ;
                g<<mij-1<<"\n" ;
                ok=1 ;
                break ;
            }
            if(v[mij]<k)
            {
                p=mij+1 ;
                max=mij ;
            }
            else
                u=mij-1 ;

        }
        if(ok==0)
        {
            while(v[max]<k)
                max++ ;
            g<<max-1<<"\n" ;

        }
    }

    if(a==2)
    {
        p=1 ;
        u=n ;
        ok=0 ;

        while(p<u)
        {
            mij=p+(u-p)/2 ;
            if(v[mij==k])
            {
                while(v[mij]==k)
                    mij-- ;
                g<<mij+1<<"\n" ;
                ok=1 ;
                break ;
            }
            if(v[mij]<k)
                p=mij+1 ;
            else
            {
                u=mij-1 ;
                max=mij ;
            }

        }
        if(ok==0)
        {
            while(v[max]>k)
                max-- ;
            g<<max+1<<"\n" ;
        }


    }
}


    return 0;
}