保序回归

题目描述

给定整数数列 a，找非降序列 a' 使 Σ|a_i-a'_i| 最小。

输入格式

第一行 n，第二行 n 个整数。

输出格式

最小偏差之和。

样例输入 #1

5
1 2 3 4 5

样例输出 #1

0

样例输入 #2

5
6 5 4 3 2

样例输出 #2

6

样例说明 #2

修改成 4 4 4 4 4。

数据范围

$1\leq n\leq 500000$，$-10^9\leq a_i\leq 10^9$。

本题涉及的知识点从属于 GESP 7级，难度等级：⭐⭐⭐⭐。

测试点分布