#include <iostream>
#include <fstream>

using namespace std;

int v[100001];
int n;

int CautareBinara( int x, int p, int u )
 {
     int m,i;

      if ( p <= u )
        {
          m = ( p + u ) / 2;

          if ( v[m] == x  )
            return m;
          else
            if ( x < v[m] ) CautareBinara( x, p, m-1 );
            else CautareBinara( x,m+1, u );
        }
       else return -1;
 }

 int Zero ( int x )
 {
     int i = CautareBinara( x, 1, n);

      while (( v[i] == x ) && ( i <= n ))
           i++;

      if ( i != -1 ) return ( i-1 );
      else return -1;

 }

 int CautareBinara2( int x, int p, int u )
 {
     int m = ( p + u ) / 2;

      if ( p == u ) return p;
      else
         if ( x < v[m] ) CautareBinara2( x, p, m-1 );
         else CautareBinara2( x, m+1, u );
        }


 int Unu ( int x )
 {
     int i = CautareBinara( x, 1, n );

     if ( i != -1 )
     {
         while (( v[i] == x ) && ( i <= n ))
               i++;
         return ( i-1 );
     }
     else
         {
             i = CautareBinara2( x, 1, n );

             if ( x < v[i] ) return i-1;
             else return i;
         }

 }

 int Doi ( int x )
 {
    int i = CautareBinara( x, 1, n );

     if ( i != -1 )
      {
        while (( v[i] == x ) && ( i >= 1 ))
              i--;
        return ( i+1 );
      }
      else
         {
             i = CautareBinara2( x, 1, n );
             if ( x > v[i] ) return i-1;
             else return i;
         }
 }

int main()
{
    int i, x, m,y;

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

     f >> n;

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

        f >> m;
       for ( i=1; i<=m; i++ )
          {
              f >> x >> y;
              if ( x == 0 )
              g << Zero(y) << "\n";
              else
               if ( x == 1 )
               g << Unu (y) << "\n";
                else
                g << Doi (y) << "\n";

          }

      return 0;
}