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

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
const int MAX_SIZE = 100000;
int v[MAX_SIZE + 1];

int binary_search_0(int left, int right, int val) {
  int division;
  while (left <= right) {
    division = (left + right) / 2;
    if (v[division] <= val) {
      left = division + 1;
    } else {
      right = division - 1;
    }
  }
  division = (left + right) / 2;
  if (v[division] > val) {
    --division;
  }
  if (v[division] == val) {
    return division;
  }
  return -1;
}

int binary_search_1(int left, int right, int val) {
  int division, n = right;
  while (left < right) {
    division = (left + right) / 2;
    if (v[division] <= val) {
      left = division + 1;
    } else {
      right = division;
    }
  }
  division = (left + right) / 2;
  if (v[division] > val) {
    --division;
  }
  return division;
}

int binary_search_2(int left, int right, int val) {
  int division;
  while (left < right) {
    division = (left + right) / 2;
    if (v[division] < val) {
      left = division + 1;
    } else {
      right = division;
    }
  }
  division = (left + right) / 2;
  if (v[division] < val) {
    ++division;
  }
  return division;
}
int main() {
  int n, m;
  fin >> n;
  for (int i = 1; i <= n; ++i ){
    fin >> v[i];
  }
  fin >> m;
  while(--m) {
    int type, value;
    fin >> type >> value;
    if (m == 0) {
      fout << binary_search_0(1, n, value) << '\n';
    }
    if (m == 1) {
      fout << binary_search_1(1, n, value) << '\n';
    }
    if (m == 2) {
      fout << binary_search_2(1, n, value) << '\n';
    }
  }
  return 0;
}