题目描述

给定一个整数数列 $a_1,\dots,a_n$ ，请找出另一个整数序列 $a'_1,\dots,a'_n$，满足 $a'_1\leq a'_2\leq\dots\leq a'_n$，使得

$$\Delta = |a_1-a'_1| + |a_2-a'_2| + \cdots + |a_n-a'_n| $$

到达最小。

输入格式

第一行：单个正整数 $n$，表示数列长度； 第二行：$n$ 个整数，表示 $a_1,\dots,a_n$。

输出格式

单个整数：表示最小的 $\Delta$，其含义见上文定义。

5
1 2 3 4 5

0

样例解释 1

不需要任何修改

5
6 5 4 3 2

6

样例解释 2

修改成4 4 4 4 4

数据范围

• 对于 $30\%$ 的数据，$n\leq 100$，$-100\leq a_i\leq 100$；
• 对于 $60\%$ 的数据，$n\leq 10000$，$-10000\leq a_i\leq 10000$；
• 对于 $100\%$ 的数据，$1\leq n\leq 500000$，$-10^{9}\leq a_i\leq 10^9$