题目描述

上校有 $n$ 枚徽章。他想将每个徽章分发给他手下的 $n$ 名士兵中的每一位。每枚徽章都有一个“炫酷度”因子，代表其持有者的成就。如果花费 1 枚硬币，可以让徽章的炫酷度增加 1。

对于任意一对士兵，其中一人应获得炫酷度严格高于另一人的徽章。也就是说，所有徽章的炫酷度应两两不同，具体的数值不重要，只要互不相同即可。

上校知道每位士兵最初该得到哪枚徽章，但现在有些徽章的炫酷度因子是相同的。请帮助他计算，为了让所有徽章的炫酷度互不相同，最少需要花费多少硬币。

输入格式

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

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

输出格式

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

输入输出样例 #1

输入 #1

4
1 3 1 4

输出 #1

1

输入输出样例 #2

输入 #2

5
1 2 3 2 5

输出 #2

2

说明/提示

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

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