#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 = 1; i <= n; i++ )
    fin >> v[i];
  fin >> m;
  while( m-- ) {
    fin >> op >> x;
    switch( op ) {
      case 0:
        rez = upper_bound( v + 1, v + n + 1, x ) - v - 1;
        if( rez <= n && x >= 1 && v[rez] == x )
          fout << rez;
        else fout << -1;
        break;
      case 1:
        rez = lower_bound( v + 1, v + n + 1, x + 1 ) - v - 1;
        fout << rez;
        break;
      default:
        rez = upper_bound( v + 1, v + n + 1, x - 1 ) - v;
        fout << rez;
    }
    fout << "\n";
  }
  return 0;
}