#include <fstream>
using namespace std;

ifstream cin("cautbin.in");
ofstream cout("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 = -1;
  while (left <= right) {
    int middle = (left + right) >> 1;
    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 = -1;
  while (left <= right) {
    int middle = (left + right) >> 1;
    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 = -1;
  while (left <= right) {
    int middle = (left + right) >> 1;
    if (v[middle] >= value) {
      position = middle;
      right = middle - 1;
    } else {
      left = middle + 1;
    }
  }
  return position;
}

int main() {
  cin >> n;
  for (int i = 1; i <= n; ++i){
    cin >> v[i];
  }
  cin >> questions;
  while(--questions) {
    int type, value;
    cin >> type >> value;
    if (type == 0) {
      cout << binary_search_0(value) << '\n';
    }
    if (type == 1) {
      cout << binary_search_1(value) << '\n';
    }
    if (type == 2) {
      cout << binary_search_2(value) << '\n';
    }
  }
  return 0;
}