CF546B.Soldier and Badges

Colonel has n badges. He wants to give one badge to every of his n soldiers. Each badge has a coolness factor, which shows how much it's owner reached. Coolness factor can be increased by one for the cost of one coin.

For every pair of soldiers one of them should get a badge with strictly higher factor than the second one. Exact values of their factors aren't important, they just need to have distinct factors.

Colonel knows, which soldier is supposed to get which badge initially, but there is a problem. Some of badges may have the same factor of coolness. Help him and calculate how much money has to be paid for making all badges have different factors of coolness.

上校有 $n$ 枚徽章。他想给自己的 $n$ 名士兵每人一枚徽章。每枚徽章都有一个“酷炫值”，表示其拥有者所达到的程度。酷炫值每次增加 1 需花费 1 枚金币。

对于任意两名士兵，其中一人所获徽章的酷炫值必须严格大于另一人的酷炫值。具体数值本身并不重要，关键是所有徽章的酷炫值必须互不相同。

上校已知最初每名士兵应分配到哪枚徽章，但存在一个问题：某些徽章的酷炫值可能相同。请帮助他计算：为使所有徽章的酷炫值互不相同，至少需要花费多少金币？

First line of input consists of one integer n (1 ≤ n ≤ 3000).

Next line consists of n integers a__i (1 ≤ a__i ≤ n), which stand for coolness factor of each badge.

输入的第一行包含一个整数 $n$（$1 \leq n \leq 3000$）。

第二行包含 $n$ 个整数 $a_i$（$1 \leq a_i \leq n$），表示每个徽章的酷炫值。

Output single integer — minimum amount of coins the colonel has to pay.

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

In first sample test we can increase factor of first badge by 1.

In second sample test we can increase factors of the second and the third badge by 1.

在第一个样例测试中，我们可以将第一个徽章的因子增加 1。

在第二个样例测试中，我们可以将第二个和第三个徽章的因子各增加 1。