No.838 Noelちゃんと星々3

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 71
作問者 : dama_mathdama_math / テスター : tatyamtatyam
5 ProblemId : 2601 / 出題時の順位表

問題文

点が$N$個あたえられます, 点$i$の高さは$Y_i$です, Noelちゃんは点の高さを自由に動かせます.
ある日Noelちゃんは, 点たちが次の条件を満たすように点を動かしたくなりました:
条件:どの点についても, その点と高さが等しいようなその点以外の点が存在する.
Noelちゃんが動かす必要のある距離の総和の最小値を求めてください.

入力

$N$
$Y_1$ $Y_2$ $\cdots$ $Y_{N-1}$ $Y_N$

1行目に点の数$N(2\leq N \leq 10^5)$が与えられます.
2行目に$N$個の整数$Y_i(−10^9\leq Y_i\leq 10^9)$が与えられます.

出力

距離の総和の最小値を整数で出力してください. 最後に改行してください.

サンプル

サンプル1
入力
7
1 2 3 4 5 6 7
出力
4

たとえば$Y_1,Y_2,Y_3$を2に, $Y_4,Y_5$を4に, $Y_6,Y_7$を6にすれば,
距離の総和が$1+0+1+0+1+0+1=4$となり最小になります.

サンプル2
入力
3
3 3 4
出力
1

$Y_3$を3にすれば距離の総和が最小となります。

サンプル3
入力
10
-3 14 15 92 65 35 89 79 32 38
出力
41
提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。