问题 B: 士兵突击

在战略电脑游戏 "定居者II "中，人们必须建造防御结构来扩大和保护领土。让我们来看看这些建筑中的一个。目前，这个防御结构正好可以容纳N个士兵。

在这个任务中，我们可以假设防御结构中的士兵数量不会增加或减少。

每个士兵都有一个军衔--从1到k的某个自然数。1代表小兵，k代表将军。士兵的等级越高，他的战斗力就越强。因此，玩家通过拥有尽可能高的军衔的士兵而获利。
为了提高士兵的军衔，他们需要训练。但士兵们不会免费训练，每次训练都需要一个金币。每次训练时，所有的N个士兵都要在场。
每次训练结束后，士兵的军衔都会增加，具体如下。首先，所有士兵被分成具有相同军衔的小组，以便形成尽可能少的小组。
然后，在军衔低于k的士兵所在的每个小组中，正好有一名士兵的军衔增加了1。
你知道此刻所有n个士兵的军衔。请确定将所有士兵的军衔提高到k级所需的金币数量。