问题 4581 --构建排列

4581: 构建排列

时间限制: 1 Sec  内存限制: 128 MB
提交: 63  解决: 45
[提交][状态][命题人:]

题目描述

整数p1p2...pn是一组有序的排列,由n个不同的正整数组成,每个整数都不超过10^9。我们将把排列p的第i个元素称为pin为排列的大小,即p1pn需出现从1n的所有正整数(无需按大小排列)。 你有一个整数序列a1a2,……an。在一次移动中,你可以使一个数字减少或增加一。计算原序列构建排列所需的最小移动次数。

输入

第一行包含整数n1n3·10^5)即排列中数字的个数。

第二行包含n个整数a1a2...an-10^9ai10^9)。

输出

输出最小移动次数。

请不要使用%lld说明符读取或写入C++中的64位整数。最好使用cincout流或%I64d说明符。 

样例输入
Copy
2
3 0
样例输出
Copy
2

提示

样例2输入

3
-1 -1 2

样例2输出

6

注释:在第一个样本中,你应该将第一个数字减少一个,然后将第二个数字增加一个。得到的排列是(2,1)。  

在第二个样本中,您需要6步来构建排列(1,3,2)。可以把其中一个-1通过2步变成1,另外一个-1通过4步变成3,最后的2保持不变,共计6步。

来源

[提交][状态]