Codeforces Round 175 (Div. 2)
C
Building Permutation
Codeforces
1200
原题
← BD →
翻译中…

Permutation $*p*$ is an ordered set of integers $*p*_{1},  *p*_{2},  ...,  *p*_{*n*}$, consisting of $*n*$ distinct positive integers, each of them doesn't exceed $*n*$. We'll denote the $*i*$-th element of permutation $*p*$ as $*p*_{*i*}$. We'll call number $*n*$ the size or the length of permutation $*p*_{1},  *p*_{2},  ...,  *p*_{*n*}$.

翻译中…

You have a sequence of integers $*a*_{1}, *a*_{2}, ..., *a*_{*n*}$. In one move, you are allowed to decrease or increase any number by one. Count the minimum number of moves, needed to build a permutation from this sequence.

翻译中…

Input

翻译中…

The first line contains integer $*n*$ ($1 ≤ *n* ≤ 3·10^{5}$) — the size of the sought permutation. The second line contains $*n*$ integers $*a*_{1}, *a*_{2}, ..., *a*_{*n*}$ ($- 10^{9} ≤ *a*_{*i*} ≤ 10^{9}$).

翻译中…

Output

翻译中…

Print a single number — the minimum number of moves.

翻译中…

Please, do not use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specifier.

翻译中…

Note

翻译中…

In the first sample you should decrease the first number by one and then increase the second number by one. The resulting permutation is $(2, 1)$.

翻译中…

In the second sample you need 6 moves to build permutation $(1, 3, 2)$.

翻译中…

样例

Input #1
2
3 0
Output #1
2
InputCopy OutputCopy
Input #2
3
-1 -1 2
Output #2
6
InputCopy OutputCopy
题目信息
题号
285C
时间限制
1 s
内存限制
256 MB
标签
贪心
模拟
排序

题面与样例版权归 Codeforces 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。