const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "input.txt")
  .toString()
  .trim()
  .split("\n");

const N = Number(input[0]); // 상근이가 가지고 있는 숫자 카드의 개수
const cards = input[1].split(" ").map(Number); // 숫자 카드에 적혀있는 정수
const M = Number(input[2]);
const targets = input[3].split(" ").map(Number); // 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수

// 상근이의 숫자 카드 정렬하기
cards.sort((a, b) => a - b);

// lowerBound는 찾고자 하는 값 이상의 숫자가 처음 나타나는 위치
function lowerBound(arr, target) {
  let left = 0;
  let right = arr.length;
  while (left < right) {
    let mid = Math.floor((left + right) / 2);
    if (arr[mid] >= target) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }
  return left;
}

// upperBound는 찾고자 하는 값을 초과하는 숫자가 처음 나타나는 위치
function upperBound(arr, target) {
  let left = 0;
  let right = arr.length;
  while (left < right) {
    let mid = Math.floor((left + right) / 2);
    if (arr[mid] > target) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }
  return left;
}

const result = [];

for (let n = 0; n < M; n++) {
  const count = upperBound(cards, targets[n]) - lowerBound(cards, targets[n]);
  result.push(count);
}
console.log(result.join(" "));

구분	lowerBound (하한)	upperBound (상한)
핵심 조건	arr[mid] >= target	arr[mid] > target
값이 같을 때 (==)	right = mid (왼쪽을 더 봄)	left = mid + 1 (오른쪽을 더 봄)
찾는 목적	target이 시작되는 위치	target을 초과하는 첫 번째 위치

function lowerBound(arr, target) {
  let left = 0;
  let right = arr.length;
  while (left < right) {
    let mid = Math.floor((left + right) / 2);
    if (arr[mid] >= target) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }
  return left;
}

• lowerBound: "너 나랑 같거나 크니? 그럼 일단 네가 오른쪽 끝이야(right = mid). 더 왼쪽에도 같은 게 있는지 확인해볼게."

function upperBound(arr, target) {
  let left = 0;
  let right = arr.length;
  while (left < right) {
    let mid = Math.floor((left + right) / 2);
    if (arr[mid] > target) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }
  return left;
}

• upperBound: "너 나보다 크니? 아니, 같다고? 그럼 넌 내가 찾는 '초과'값이 아니야. 더 오른쪽으로 가야 해(left = mid + 1)."

왜 둘 다 left를 리턴하나요?

while (left < right) 방식의 이분 탐색은 left와 right가 같아지는 순간 루프가 종료됩니다.

1. 루프가 종료될 때 항상 left === right 상태입니다.
2. 따라서 return left;를 하나 return right;를 하나 결과는 똑같습니다. (관습적으로 left를 많이 사용합니다.)
3. 이 left 값은 루프가 진행되면서 조건을 만족하는 경계선으로 계속 수렴해온 최종 위치가 됩니다.

예시로 보는 리턴값의 차이

배열 [1, 2, 2, 2, 3]에서 target = 2를 찾는다고 가정해 봅시다.

lowerBound의 흐름:

1. mid가 인덱스 2(값 2)일 때, arr[mid] >= 2가 참이므로 right = 2가 됩니다.
2. 계속 범위를 좁히다 보면 결국 2가 처음 나타나는 인덱스 1에서 left와 right가 만납니다.
3. 결과: 1

upperBound의 흐름:

1. mid가 인덱스 2(값 2)일 때, arr[mid] > 2가 거짓이므로 left = mid + 1 (인덱스 3)이 됩니다.
2. 계속 오른쪽으로 가다 보면 결국 2를 초과하는 3이 처음 나타나는 인덱스 4에서 left와 right가 만납니다.
3. 결과: 4

이분탐색에 대한 대전제

1. 오름차순으로 정렬 필수

2. '경계값'을 찾는 두 가지 함수

   단순히 target을 찾는 binary_search만으로는 중복된 숫자의 개수를 효율적으로 알 수 없습니다. 대신 리스트 내에서 target이 시작되는 지점과 끝나는 지점을 찾아야 합니다.

   • Lower Bound (하한): 찾고자 하는 값 K보다 같거나 큰 숫자가 처음 나타나는 위치.
   • Upper Bound (상한): 찾고자 하는 값 K보다 큰 숫자가 처음 나타나는 위치.

3. 개수 계산의 원리

   위의 두 위치를 정확히 찾았다면, 해당 숫자의 개수는 아주 간단한 산수로 구할 수 있습니다.개수 = Upper Bound index - Lower Bound index
   예를 들어, [1, 2, 2, 2, 3]에서 숫자 2를 찾는다면:

   • Lower Bound는 인덱스 1 (첫 번째 2의 위치)
   • Upper Bound는 인덱스 4 (2보다 큰 3이 처음 나타나는 위치)
   • 개수: 4 - 1 = 3개