样例下载

题目描述

给出一个含有 $n$ 个元素的数列 $A$，让你构造同样含有 $n$ 个元素的数列 $B$，要求：

• 对于 ∀ $1 ≤ i < j ≤ n$，有 $B_i ≤ B_j$ 或 $B_i ≥ B_j$

构造完后，定义 $S = \sum_{i=1}^n |Ai-Bi|$。

如何构造，可以使得 S 的值尽可能的小？你只需要输出可以得到的 S 的最小值。

输入格式

第一行：一个整数 $n$。

接下来 $n$ 行：每行一个整数 $A_i$。

输出格式

一个整数，表示答案。

样例输入

7
1
3
2
4
5
3
9

样例输出

3

数据范围

100% 的数据：$1 ≤ n ≤ 2 · 10^3$, $0 ≤ A_i ≤ 10^9$