CF546B Soldier and Badges

上校有 $n$ 枚徽章。他想将每个徽章分发给他手下的 $n$ 名士兵中的每一位。每枚徽章都有一个“炫酷度”因子，代表其持有者的成就。如果花费 1 枚硬币，可以让徽章的炫酷度增加 1。 对于任意一对士兵，其中一人应获得炫酷度严格高于另一人的徽章。也就是说，所有徽章的炫酷度应两两不同，具体的数值不重要，只要互不相同即可。 上校知道每位士兵最初该得到哪枚徽章，但现在有些徽章的炫酷度因子是相同的。请帮助他计算，为了让所有徽章的炫酷度互不相同，最少需要花费多少硬币。

输入的第一行包含一个整数 $n$（$1 \leq n \leq 3000$）。 第二行包含 $n$ 个整数 $a_{i}$（$1 \leq a_{i} \leq n$），表示每枚徽章的炫酷度因子。

输出一个整数——上校需要支付的最小硬币数。

在第一个样例中，我们可以将第一枚徽章的因子增加 $1$。 在第二个样例中，我们可以将第二枚和第三枚徽章的因子各增加 $1$。 由 ChatGPT 5 翻译