上校有 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。