/**
 * @Author: catalin
 * @Date:   15-Apr-2019
 * @Last modified by:   catalin
 * @Last modified time: 24-Apr-2019
 */
#include <fstream>
#include <iostream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
const int NMAX = 100011;
int v[NMAX];
/*
bsearch0:descriere
Functia returneaza cea mai mare pozitie pe care se afla un element cu valoare
key sau -1 daca aceasta valoare nu se gaseste in sir
METODA CLASICA MODIFICATA
*/
int bsearch0(int p, int u, int key) {
  int m;
  while (p <= u) {
    m = (p + u) / 2;

    // m = p + (u - p) / 2;
    if (v[m] <= key)
      p = m + 1;
    else
      u = m - 1;
  }
  m = (p + u) / 2;

  // m = p + (u - p) / 2;
  if (v[m] > key)
    m--;
  if (v[m] == key)
    return m;
  return -1;
}
int bsearch1(int p, int u, int key) {
  int m;
  while (p < u) {
    m = (p + u) / 2;

    // m = p + (u - p) / 2;
    if (v[m] <= key)
      p = m + 1;
    else
      u = m;
  }
  m = (p + u) / 2;

  // m = p + (u - p) / 2;
  if (v[m] > key)
    --m;
  return m;
}
int bsearch2(int p, int u, int key) {
  int m;
  while (p < u) {
    m = (p + u) / 2;
    // m = p + (u - p) / 2;
    if (v[m] < key)
      p = m + 1;
    else
      u = m;
  }
  m = (p + u) / 2;

  // m = p + (u - p) / 2;
  if (v[m] < key)
    ++m;
  return m;
}
int main() {
  int n, m, tip, val;
  /*
  n:numarul de valori citite din fisier
  v:vectorul de valori indexat de la 1
  tip:tipul operatiunii
  val:valoarea citita
  */
  fin >> n;
  for (int i = 1; i <= n; ++i)
    fin >> v[i];
  fin >> m;
  for (int i = 0; i < m; ++i) {
    fin >> tip >> val;
    if (tip == 0) {
      fout << bsearch0(1, n, val) << "\n";
    } else if (tip == 1) {
      fout << bsearch1(1, n, val) << "\n";
    } else if (tip == 2) {
      fout << bsearch2(1, n, val) << "\n";
    }
  }
  fin.close();
  fout.close();
  return 0;
}