最小二叉堆(通常简称为“小根堆”)是计算机科学中一种基于二叉树的特殊数据结构。它是一棵具有以下两个主要性质的二叉树:
- 堆性质:在小根堆中,对于任意给定的节点,该节点的值小于或等于其子节点的值。这意味着堆中的最小值总是位于根节点。换句话说,堆中最小的元素在最顶部。
- 二叉树结构:小根堆通常是一棵完全二叉树,这意味着除了最后一层外,树的所有层都被完全填满,而最后一层则是从左到右填充的。这种结构特性使得小根堆可以高效地使用数组来实现。
小根堆常用于实现优先队列,优先队列是一种维护具有关联优先级的元素集合的数据结构。通过将最小元素保持在根节点,小根堆可以在对数时间内快速检索并删除具有最高优先级(最小值)的元素。然而,从小根堆中删除任何其他元素可能需要线性时间。
Hank 最近学习了小根堆。他想知道,在一个包含 $n$ 个节点的小根堆中,有多少个节点可以存放第 $k$ 小的元素。请编写一个程序来帮助他。
输入格式
输入包含两个空格分隔的正整数 $n$ 和 $k$。
输出格式
输出在一个包含 $n$ 个节点的小根堆中,可以存放第 $k$ 小的元素的节点数量。
数据范围
$1 \le k \le n \le 10^{18}$
样例
输入样例 1
100 1
输出样例 1
1
输入样例 2
12 3
输出样例 2
6