题目描述

高橋君と青木君の家の庭には草 $1$, 草 $2$, $\ldots$, 草 $N$ の $N$ 本の草が生えており、草 $i$ の高さは $A_i$ です。 高橋君と青木君は次の方法で庭の草抜きを行う事にしました。

• まず、青木君が高々 $K$ 本の草を選んで抜く。

• その後、高橋君が次の操作を庭の草がすべて抜けるまで繰り返す。

  • 残っている草のうち高さが最大のものの高さを $H$ とする。残っている草のうち、高さが $\frac{H}{2}$ より高いものを一斉に抜く。

青木君は、高橋君の操作回数が最小となるようにした上で、自分の抜く本数を最小にしたいと考えています。 このときの高橋君の操作回数と青木君の抜く草の本数を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

高橋君の操作回数と青木君の抜く草の本数をこの順に空白区切りで出力せよ。

题目大意

有 $n$ 株草，第 $i$ 株的高度为 $a_i$，你可以预先拔掉不超过 $k$ 株草，然后按如下方式操作：

• 选取没拔掉的草中最高的草（高度 $h$）,一次拔掉所有高度 $>\lfloor \frac{h}{2}⌋$ 的草。

你需要在操作次数最少的情况下，最小化预先拔掉的草的数量。

4 1
2 3 4 9

2 1

3 3
2 3 5

0 3

9 8
137 55 56 60 27 28 133 56 55

1 4

提示

制約

• $1\ \leq\ N\ \leq\ 2\times\ 10^5$
• $0\ \leq\ K\ \leq\ N$
• $1\ \leq\ A_i\ \leq\ 10^9$
• 入力は全て整数である。

Sample Explanation 1

例えば青木君が草 $4$ (高さ $9$) を選んで抜いたとき、残りの草の中で最も高いものは草 $3$ であり、その高さは $4$ です。 $\frac{4}{2}=2$ であり、$2\ <\ 3$, $2\ <\ 4$ より $1$ 回目の操作で高橋君は草 $2$ と草 $3$ のみを抜くことができます。その後、 $2$ 回目の操作で草 $1$ を抜き、高橋君は $2$ 回で操作を終えることができます。 一方で、青木君がどの草を $1$ 本選んだとしても高橋君は $1$ 回で操作を終えることはできません。 また、もし青木君が $1$ 本も抜かなかったとすると高橋君は $3$ 回操作する必要があるため、青木君は高橋君の操作回数を最小にするために最低 $1$ 本は抜かなくてはなりません。

Sample Explanation 2

青木君が全ての草を抜いたとき高橋君は操作を行う必要がなく、明らかにこのときが最小です。