힙 구조

최소 이진 힙(min-heap)은 컴퓨터 과학에서 널리 쓰이는 이진 트리 기반 자료구조다. 주요 성질은 두 가지다.

1. 힙 성질: 임의의 노드의 값은 그 노드의 자식 노드 값보다 작거나 같다. 따라서 힙의 최솟값은 항상 루트에 있다. 가장 작은 원소는 항상 맨 위에 있다.
2. 이진 트리 구조: 최소 힙은 보통 완전 이진 트리다. 마지막 레벨을 제외한 모든 레벨이 가득 차 있고, 마지막 레벨은 왼쪽부터 채워진다. 이 구조 덕분에 최소 힙을 배열로 효율적으로 구현할 수 있다.

최소 힙은 우선순위가 붙은 원소의 모음을 관리하는 우선순위 큐를 구현하는 데 자주 쓰인다. 최솟값을 루트에 두므로, 최소 힙은 우선순위가 가장 높은(값이 가장 작은) 원소를 로그 시간에 꺼내고 제거할 수 있다. 다른 원소를 제거하는 데는 선형 시간이 걸릴 수 있다.

Hank는 최근 최소 힙을 배웠다. 그는 n개의 노드로 이루어진 최소 힙에서 k번째로 작은 원소를 보관할 수 있는 노드가 몇 개인지 궁금해한다. 그를 도와줄 프로그램을 작성하라.

공백으로 구분된 두 개의 양의 정수 $n$과 $k$가 주어진다.

n개의 노드로 이루어진 최소 힙에서 k번째로 작은 원소를 보관할 수 있는 노드의 개수를 출력한다.

$1≤k≤n≤10^{18}$

모든 원소가 서로 다르다고 가정한다.