#include <cstdlib>
#include <fstream>
#define Nmax 100111

/*
 *
 */
int main( void )
{
    int v[Nmax];
    int N, M, i, j, z, left, right, middle;
    std::ifstream in( "cautbin.in" );
    in>>N;
    for( i=1; i <= N; ++i )
        in>>v[i];
    std::ofstream out( "cautbin.out" );
    for( in>>M; M; --M )
    {
        in>>i>>j;
        z=-1;
        left=1; right=N;
        while( left <= right )
        {
            middle=left+(right-left)/2;
            if( 0 == i )
            {
                if( j == v[middle] )
                {
                    z=middle;
                }
                if( j < v[middle] )
                    right=middle-1;
                else left=middle+1;
            }
            else if( 1 == i )
                 {
                     if( j >= v[middle] )
                     {
                         if( -1 == z || z < middle )
                            z=middle;
                         left=middle+1;
                     }
                     else right=middle-1;
                 }
                 else if( 2 == i )
                      {
                          if( j <= v[middle] )
                          {
                              if( -1 == z || z > middle )
                                z=middle;
                              right=middle-1;
                          }
                          else left=middle+1;
                      }
        }
        out<<z<<'\n';
    }
    return EXIT_SUCCESS;
}