在一款战略电脑游戏“工人物语 II”中,玩家必须建造防御结构来扩大和保护领土。让我们以其中一栋建筑为例。目前防御结构正好可容纳n名士兵。在此任务中,我们可以假设防御结构中的士兵数量不会增加或减少。
每个士兵都有一个军衔——从 1 到 k 的某个自然数。 1代表私人,k代表将军。士兵的军衔越高,战斗力就越强。因此,玩家可以从拥有最高等级的士兵中获益。
增加他们需要训练的士兵的等级。但士兵们不会免费训练,每次训练都需要一枚金币。每次训练都有 n 名士兵参加。
在每次训练结束时,士兵的军衔增加如下。首先将所有士兵分成同等等级的小组,从而形成尽可能少的小组。然后,在k级以下士兵所在的每个组中,恰好有一名士兵将其军衔提升一级。
你知道目前所有n名士兵的军衔。求出将所有士兵的军衔提升到k级所需的金币数量。
输入
第一行包含两个整数 n 和 k (1 ≤ n, k ≤ 100)。它们分别代表士兵的数量和相应的不同军衔的数量。第二行包含 n 个按非递减顺序排列的数字。其中第i个ai代表防御建筑中第i个士兵的军衔(1≤i≤n,1≤ai≤k)。
输出
打印一个整数——将所有士兵提升到最高等级所需的金币数量。
示例
输入 #1
4 4 1 2 2 3
输出 #1
4
输入 #2
4 3 1 1 1 1
输出 #2
5
注意
在第一个示例中,排名将按以下方式提升:
1 2 2 3 → 2 2 3 4 → 2 3 4 4 → 3 4 4 4 → 4 4 4 4
因此总共需要4个金币的训练课程4次。