#182. Making the Grade

Making the Grade

题目描述

给定序列 A,将它改为一个非递减或非递增的整数序列 B,代价是所有 |Ai−Bi| 的和。求最小代价。相等的相邻元素允许存在。

输入格式

第一行 N≤2000;随后 N 个整数 Ai,0≤Ai≤10^9。

输出格式

输出最小总代价。

样例输入

7
1
3
2
4
5
3
9

样例输出

3

题意整理;原题与输入输出格式对照。