#include <iostream>
#include <cstdio>
#include <fstream>

using namespace std;

int binarySearch1 (int array[], int length, int target) { //determina cea mai mare pozitie lui target
  int left = -1;
  int right = length;
  
  while (right - left > 1) {
    int middle = left + (right - left) / 2;
    if (array[middle] > target) right = middle;
    else left = middle;
  }
  
  if (left != -1 && target == array[left]) return left;
  else return -1;
}

int binarySearch2 (int array[], int length, int target) { //determina cea mai mare pozitie a unui element mai mic sau egal decat target
  int left = -1;
  int right = length;
  
  while (right - left > 1) {
    int middle = left + (right - left) / 2;
    if (array[middle] > target) right = middle;
    else left = middle;
  }
  
  if (left != -1 && target >= array[left]) return left;
  else return -1;
}

int binarySearch3 (int array[], int length, int target) { //determina cea mai mica pozitie a unui element mai mare sau egal decat target
  int left = -1;
  int right = length;
  
  while (right - left > 1) {
    int middle = left + (right - left) / 2;
    if (array[middle] >= target) right = middle;
    else left = middle;
  }
  
  if (right != length && target <= array[right]) return right;
  else return -1;
}


int main () {

  
  freopen("cautbin.in", "r", stdin);
  freopen("cautbin.out", "w", stdout);

  int N;
  scanf ("%d", &N);

  int array[10000];
  for (int i = 1; i <= N; i++) {
    scanf("%d ", &array[i]);      
  }

  int M;
  scanf ("%d", &M);
  
  int quiz, target;
  for (int i = 0; i < M; i++) {
    scanf ("%d %d", &quiz, &target);
   
    if (quiz == 0) {
      printf ("%d \n", binarySearch1(array, N, target));
    }

    if (quiz == 1) {
      if (target == array[N-1] || target > array[N-1]) 
      printf ("%d \n", N);
      else if (target == array[0] || target < array[0]) 
      printf ("0\n");
      else printf ("%d \n", binarySearch2(array, N, target));
    }

    if (quiz == 2) {
      if (target == array[N-1] || target > array[N-1]) 
      printf ("%d \n", N);
      else if (target == array[0] || target < array[0]) 
      printf ("0\n");
      else printf ("%d \n", binarySearch3(array, N, target));
    }
  }

return 0;
}