#include <fstream>
#include <cstdlib>
#define N_MAX 100011

using namespace std;

int v[N_MAX];

inline int _max( int x, int y ) { return x >= y ? x : y; }
inline int _min( int x, int y ) { return x <= y ? x : y; } 
int main()
{
    int N, M, i, op, x, p, left, middle, right;
    ifstream in("cautbin.in");
    ofstream out("cautbin.out");
    
    in>>N;
    for( i=1; i <= N; ++i )
       in>>v[i];
    for( in>>M; M; --M )
    {
       in>>op>>x;
       p=-1;
       left=1; right=N;
       if( 0 == op )
       {
          while( left <= right )
          {
             middle=(left+right)>>1;
             if( x == v[middle] )
               p=_max( p, middle );
             if( x >= v[middle] )
               left=middle+1;
             else right=middle-1;
          }
       }
       else if( 1 == op )
            {
               while( left <= right )
               {
                  middle=(left+right)>>1;
                  if( x >= v[middle] )
                  {
                     p=_max( p, middle );
                     left=middle+1;
                  }
                  else right=middle-1;  
               }
            }
            else if( 2 == op )
                 {
                    p=N+1;
                    while( left <= right )
                    {
                       middle=(left+right)>>1;
                       if( x <= v[middle] )
                       {  
                          p=_min( middle, p );
                          right=middle-1;
                        }
                        else left=middle+1;
                    }
                 }
       out<<p<<'\n';
    }
    
    return EXIT_SUCCESS;
}