#include <iostream>
#include <fstream>
using namespace std;

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

int v[100001] , n , op , val ;

void scan()
{
     in >>  n ;
     for ( int i =1 ; i<= n ; ++ i )
          in >> v[i];
           in >> op ;
}

int caut_bin0(int left , int right )
{   int m ;  int p = -1 ;
    while ( left <= right)
    {int m = (left+right) / 2 ;

        if(v[m] <= val )
        {
             if(v[m]==val)p=m;
                left = m +1;
        }
        else right = m - 1 ;
    }
return p ;
}

int caut_bin1( int left , int right )
{
    int m  ;  int p = -1 ;

    while (left <= right )
    {
        m = (left + right ) / 2 ;

        if (v[m] <= val )
        {
             p = m ;
              left = m + 1 ;
        }

        else right = m-1;
    }
    return p ;


}

int caut_bin3( int left, int right )
{
    int m , p = -1 ;

    while ( left <= right )
    {
         m = (left + right )/ 2;

         if (v[m]>= val)
         {
              p = m ;
              right  = m -1 ;
         }

        else left = m + 1 ;
    }
    return p ;

}



int main()
{scan();
   for ( int i =1 ; i<= op ; ++ i )
   {
       int C , x ;
        in >> C >> val ;
           if (!C)
                  {
                      int poz = caut_bin0(1,n);
                         out << poz << "\n";
                  }
             else if ( C == 1 )
             {
                   int poz = caut_bin1(1,n);
                      out << poz << "\n";
             }

             else if ( C == 2 )
             {
                 int poz = caut_bin3(1,n);
                   out << poz << "\n";
             }

   }




    return 0;
}