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

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

int binary_search_0 (int value) {
  int left = 1, right = n, position = 0;
  while (left <= right) {
    int middle = (left + right) / 2;
    if (v[middle] <= value) {
      position = middle;
      left = middle + 1;
    } else {
      right = middle - 1;
    }
  }
  if (v[position] == value) {
    return position;
  }
  return -1;
}

int binary_search_1 (int value) {
  int left = 1, right = n, position = 0;
  while (left <= right) {
    int middle = (left + right) / 2;
    if (v[middle] <= value) {
      position = middle;
      left = middle + 1;
    } else {
      right = middle - 1;
    }
  }
  return position;
}

int binary_search_2 (int value) {
  int left = 1, right = n, position = 0;
  while (left <= right) {
    int middle = (left + right) / 2;
    if (v[middle] >= value) {
      position = middle;
      right = middle - 1;
    } else {
      left = middle + 1;
    }
  }
  return position;
}

int main() {
  fin >> n;
  for (int i = 1; i <= n; ++i){
    fin >> v[i];
  }
  fin >> questions;
  while(--questions) {
    int type, value_given;
    fin >> type >> value_given;
    if (type == 0) {
      fout << binary_search_0(value_given) << '\n';
    } else if (type == 1) {
      fout << binary_search_1(value_given) << '\n';
    } else {
      fout << binary_search_2(value_given) << '\n';
    }  
  }
  return 0;
}