#P18469. Bladestorm
Bladestorm
Bladestorm
在《炉石传说》中,Bladestorm(剑刃风暴)是一张强力的战士职业法术牌,如下图所示。它的效果是:对所有随从造成 1 点伤害,重复这一过程,直到有随从死亡。

在实际对局中,仅靠 Bladestorm 往往不足以处理复杂的场面,因此通常还会配合其它范围伤害法术使用。现在 Bobo 正在使用战士职业,对手依次打出 个随从,其生命值为两两不同的 ,且 。
Bobo 拥有无限张 Bladestorm,以及无限张能够对所有随从造成 点伤害的普通范围伤害法术。他可以按任意顺序使用任意数量的法术。每当对手打出一个随从,他都想知道:此时要清除场上所有随从,至少需要使用多少张法术?
形式化地,对每个 ,令 。求将 变为空集所需的最少操作次数 。允许以下两种操作:
- 使用一次 Bladestorm:
- 对每个 ,令 。
- 如果此时 中有元素为 ,删去其中所有的 ,结束这一次操作;否则重复上一小步。
- 使用一次普通范围伤害法术:对每个 ,令 ,并删去所有不大于 的元素。
每个前缀的答案分别从该前缀的原生命值集合出发计算。
输入格式
输入包含多组测试用例。第一行包含整数 ()。
每个测试用例的第一行包含整数 (),分别表示随从数量和普通范围伤害法术造成的伤害。
第二行包含 个两两不同的整数 (),表示随从被依次打出时的生命值。
保证所有测试用例的 之和不超过 。
输出格式
对于每个测试用例,输出一行 个整数 $\mathrm{ans}_1,\mathrm{ans}_2,\ldots,\mathrm{ans}_n$,第 个整数表示对手打出前 个随从后,清除这些随从所需的最少法术数。
完整原样例输入
3
7 2
4 7 3 6 1 2 5
11 3
10 7 4 9 6 8 5 1 3 2 11
9 2
1 2 3 7 8 9 4 5 6
完整原样例输出
1 2 3 3 4 4 4
1 2 3 3 3 3 3 4 4 4 4
1 1 2 3 4 4 4 5 5