OI题库

2008 年 5 月 12 日 14 时 28 分，国难时刻， 8.0 级地震灾难突降四川。条条道路被震裂或被巨石和泥石流斩断，座座桥梁被震裂或震垮，座座隧道被撕裂震坏。交通完全瘫痪了，灾区同胞在生死呼唤，生命之路啊，告急！告急！告急！

要想救援物资尽快运送，必须先第一时间修好通往汶川的道路，因此，在地震发生后，有关部门便展开大力抢修。假设修好后的路面高度应当单调上升或单调下降（也就是说，高度上升与高度下降的路段不能同时出现在修好的路中），这样的道路车辆通过的速度将是无穷大（接近光速），货物将在最短的时间内运到灾区。

然而整条路被地震震成了 N 段， N 个整数 A1,…,A N （ 1 ≤ N ≤ 2000 ）依次描述了每一段路的高度（ 0 ≤ Ai ≤ 1000000000 ）。希望找到一个恰好含 N 个元素的不上升或不下降序列 B1,…,Bn, 作为修过的路中每个路段的高度。

由于将每一段路垫高或挖低一个单位的花费相同，修路的总支出可以表示为：

|A1-B1|+|A2-B2|+ … +|An-Bn|

请你计算一下，要修好这段路，在这项工程上的最小支出是多少？总支出不会超过 2^31-1 。

[ 输入格式 ]

输入文件的第一行为一个整数 N ，以下 n 行每行一个整数 Ai ，表示路面的高度。

[ 输出格式 ]

输出文件仅有一个整数，表示如果把路修成高度不上升或高度不下降的最小花费。

[ 输入样例 ]

7
1
3
2
4
5
3
9

[ 输出样例 ]

3

[ 输出说明 ]

将第一个高度为 3 的路段的高度减少为 2 ，将第二个高度为 3 的路段高度增加到 5 ，总花费为 |2-3|+|5-3|=3 ，并且各路段的高度为一个不下降序列 1 ， 2 ， 2 ， 4 ， 5 ， 5 ， 9 。