#include <fstream>

#define NMAX 100005

using namespace std;

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

int v[NMAX] ;

int n,m,logn ;

int main()
{
    int cod,i,x,lg ;

    f>>n ;
    for(i=1;i<=n;i++)
        f>>v[i] ;


    logn=1 ;
    while(logn<=n)
        logn=logn<<1 ;

    f>>m ;

    for(int q=1;q<=m;q++)
    {
        f>>cod>>x ;
        if(cod<2)
        {
            i=0 ;
            lg=logn ;
            while(lg)
            {
                if(i+lg<=n&&v[i+lg]<=x)
                    i+=lg ;
                lg=lg>>1 ;
            }

            if(cod==0&&v[i]!=x)
                g<<"-1\n" ;
            else
                g<<i<<'\n' ;
        }
        else
        {
            i=n ;
            lg=logn ;
            while(lg)
            {
                if(i-lg>0&&v[i-lg]>=x)
                    i-=lg ;
                lg=lg>>1 ;
            }

            g<<i<<'\n' ;


        }


    }






    return 0;
}