杂草

题目描述

高桥君和青木君的花园里长着 $N$ 株杂草,称为杂草 $1$,杂草 $2$,$\ldots$,杂草 $N$。杂草 $i$ 的高度为 $A_i$。 他们决定按如下方式拔除这些杂草:

首先,青木君最多选择 $K$ 株杂草并将它们拔掉。

然后,高桥君重复执行以下操作,直到所有杂草被拔光。

设 $H$ 为剩余杂草中最高的高度。一次性拔掉所有高度高于 $\frac{H}{2}$ 的杂草。

青木君想要最小化高桥君的操作次数。此外,他还希望在操作次数最小的情况下,尽量少拔杂草。 求高桥君的操作次数和此时青木君拔掉的杂草株数。

输入格式

输入按以下格式从标准输入给出:

$N$ $K$
$A_1$ $A_2$ $\ldots$ $A_N$

输出格式

按顺序输出高桥君的操作次数和青木君拔掉的杂草株数,中间用空格分隔。

样例

4 1
2 3 4 9

2 1

例如,假设青木君选择高度为 $9$ 的杂草 $4$ 并拔掉。此时,剩余杂草中最高的草是高度为 $4$ 的杂草 $3$。 有 $\frac{4}{2}=2$,由于 $2 \lt 3$ 且 $2 \lt 4$,高桥君在第一次操作中拔掉杂草 $2$ 和 $3$。然后,他在第二次操作中拔掉杂草 $1$,共两次操作完成工作。 另一方面,无论青木君选择拔掉哪一株杂草,都无法在 1 次操作内完成。

另外,如果青木君一株杂草都不拔,高桥君将需要 3 次操作,所以为了最小化高桥君的操作次数,青木君至少需要拔掉 1 株杂草。

3 3
2 3 5

0 3

如果青木君拔掉所有杂草,高桥君需要做 0 次操作,这显然是最小的可能次数。

9 8
137 55 56 60 27 28 133 56 55

1 4

数据范围

• $1 \le N \le 2 \times 10^5$
• $0 \le K \le N$
• $1 \le A_i \le 10^9$
• 输入均为整数