#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
const int MAXN = 1e5;

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

int v[MAXN+1];
int main() {
  int n, i, op, x, m, rez;
  fin >> n;
  for( i = 0; i < n; i++ )
    fin >> v[i];
  fin >> m;
  while( m-- ) {
    fin >> op >> x;
    switch( op ) {
      case 0:
        if( *lower_bound( v, v + n, x ) == n )
          fout << -1;
        else {
          rez = *upper_bound( v, v + n, x ) - 1;
          if( v[rez] > x )
            rez--;
          fout << rez + 1;
        }
        break;
      case 1:
        rez = *upper_bound( v, v + n, x ) - 1;
        if( v[rez] > x )
          rez--;
        fout << rez + 1;
        break;
      default:
        if( *lower_bound( v, v + n, x ) == n ) {
          rez = *upper_bound( v, v + n, x );
          if( v[rez-1] > x )
            rez--;
          fout << rez + 1;
        }
        else {
          rez = *lower_bound( v, v + n, x );
          while( v[rez] == x )
            rez--;
          fout << rez + 2;
        }
    }
    fout << "\n";
  }
  return 0;
}