#include <stdio.h>
#include <stdlib.h>

int find(int *list, int list_length, int subject);
int binary_search(int *list, int min, int max, int subject);
int answer(int *list, int position, int type);
int biggest_subject(int *list, int position);
int smaller_than_subject(int *list, int position);
int greather_than_subject(int *list, int position);

int main() {
  FILE *input, *output;
  int list_length, count, result, index, type, subject, position;
  int *list;

  input  = fopen("cautbin.in",  "r");
  output = fopen("cautbin.out", "w");

  fscanf(input, "%d\n", &list_length);

  list = (int*) malloc(sizeof(int) * list_length);

  for(index = 0; index < list_length; index += 1) {
    fscanf(input, "%d", &list[index]);
  }

  fscanf(input, "%d\n", &count);

  for(index = 0; index < count; index += 1) {
    fscanf(input, "%d %d", &type, &subject);

    position = find(list, list_length, subject);
    result   = answer(list, position, type);

    fprintf(output, "%d\n", result);
  }

  fclose(input);
  fclose(output);

  return 0;
}

int find(int *list, int list_length, int subject) {
  binary_search(list, 0, list_length, subject);
}

int binary_search(int *list, int min, int max, int subject) {
  if (min == max) {
    if (list[min] == subject) {
      return min;
    } else {
      return -1;
    }
  }

  int position = (min + max) / 2;

  if (list[position] == subject) {
    return position;
  } else if (list[position] < subject ) {
    return binary_search(list, min, position - 1, subject);
  } else {
    return binary_search(list, position + 1, max, subject);
  }
}

int answer(int *list, int position, int type) {
  switch (type) {
    case 0:
      if (position == -1) return -1;
      return biggest_subject(list, position);
    case 1:
      return greather_than_subject(list, position);
    case 2:
      return smaller_than_subject(list, position);
  }
}

int biggest_subject(int *list, int position){
  int element = list[position];

  while (element == list[position]) position += 1;

  return position;
}

int smaller_than_subject(int *list, int position){
  int element = list[position];

  while (element == list[position]) position -= 1;

  return position + 2;
}

int greather_than_subject(int *list, int position){
  int element = list[position];

  while (element == list[position]) position += 1;

  return position;
}