#include <stdio.h>
#define MAXN 100010

int bin0(int *v, int left, int right, int key){
  
  int mid;

  while(left < right){
    mid = left+(right-left)/2;
    if(v[mid] <= key)
      left  = mid+1;
    else
      right = mid-1;
  }
  mid = left+(right-left)/2;

  if(v[mid] > key)
    mid--;
  if(v[mid] == key)
    return mid;
  return -2;

}
int bin1(int *v, int left, int right, int key){

  int mid;

  while(left < right){
    mid = left+(right-left)/2;
    if(v[mid] <= key)
      left  = mid+1;
    else
      right = mid-1;
  }
  mid = left+(right-left)/2;

  if(v[mid] > key)
    mid--;
  return mid;

}
int bin2(int *v, int left, int right, int key){

  int mid;

  while(left < right){
    mid = left+(right-left)/2;
    if(v[mid] >= key)
      right = mid-1;
    else
      left  = mid+1;
  }
  mid = left+(right-left)/2;

  if(v[mid] < key)
    mid++;
  return mid;

}

int main(){

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

  int N, M, i, v[MAXN], type, key;

  scanf("%d", &N);
  for(i  = 0; i < N; i++)
    scanf("%d", v+i);

  scanf("%d", &M);
  while(M--){
    scanf("%d %d", &type, &key);
    if(type == 0)
      printf("%d\n", bin0(v, 0, N-1, key)+1);
    if(type == 1)
      printf("%d\n", bin1(v, 0, N-1, key)+1);
    if(type == 2)
      printf("%d\n", bin2(v, 0, N-1, key)+1);
  }

  return 0;

}