抢修道路

Grade 0 Open Time Thursday, 21 February 2013, 11:02 pm
Discount 0.8 Time Discount Thursday, 28 February 2013, 11:02 pm
Allow late Yes Close Time Thursday, 28 February 2013, 11:02 pm
Input file roady.in Output file roady.out

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 。