← 返回题目列表

Codeforces · 546/B

B. 士兵和徽章

中文机器翻译题面 查看原题

上校有 n 枚徽章。他想给他的n名士兵每人一枚徽章。每个徽章都有一个酷度系数,表明它的拥有者达到了多少。花费一枚硬币即可将酷度系数提高一倍。

对于每对士兵,其中一个应该获得一枚徽章,其系数严格高于第二个。它们的因子的确切值并不重要,它们只需要具有不同的因子即可。

上校知道哪个士兵最初应该获得哪个徽章,但有一个问题。有些徽章可能也有同样的酷感。帮助他计算一下要花多少钱才能使所有徽章具有不同的酷度。

输入

输入的第一行由一个整数 n (1 ≤ n ≤ 3000) 组成。

下一行由 n 个整数 ai (1 ≤ ai ≤ n) 组成,代表每个徽章的酷度系数。

输出

输出单个整数——上校必须支付的最小硬币数量。

示例

输入 #1

4
1 3 1 4

输出 #1

1

输入 #2

5
1 2 3 2 5

输出 #2

2

注意

在第一个样本测试中,我们可以将第一个徽章的系数增加 1。

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