#include <iostream>
#include <fstream>
using namespace std;

int cautareBinara(int sir[100001], int element, int tip, int marime_sir) {
  int min = 0, max = marime_sir, medie, biggest_pos = -1;
  switch(tip) {
    case 0: {
      while(min <= max) {
        medie = min + (max - min) / 2;
        if(sir[medie] == element && medie > biggest_pos) {
          biggest_pos = medie;
        }
        min = medie + 1;
      }
      return biggest_pos;
    }
    case 1: {
      while(min <= max) {
        medie = min + (max - min) / 2;
        if(sir[medie] <= element) {
          biggest_pos = medie;
        }
        min = medie + 1;
      }
      return biggest_pos;
    }
    case 2: {
      while(min <= max) {
        medie = min + (max - min) / 2;
        if(sir[medie] >= element) {
          biggest_pos = medie;
        }
        max = medie - 1;
      }
      return biggest_pos;
    }
  }
  return -1;
}

int main() {
  ifstream fin("cautbin.in");
  ofstream fout("cautbin.out");
  int elements, nr_intrebari, tip_intrebare, sir[100001], element;
  fin >> elements;
  for(int i = 1; i <= elements; i++) {
    fin >> sir[i];
  }
  fin >> nr_intrebari;
  for(int i = 0; i < nr_intrebari; i++) {
    fin >> tip_intrebare;
    if(tip_intrebare == 0) {
      fin >> element;
      fout << cautareBinara(sir, element, 0, elements);
    }
    else if(tip_intrebare == 1) {
      fin >> element;
      fout << cautareBinara(sir, element, 1, elements);
    }
    else if(tip_intrebare == 2) {
      fin >> element;
      fout << cautareBinara(sir, element, 2, elements);
    }
    if(i < nr_intrebari - 1) {
      fout << "\n";
    }
  }
  return 0;
}