[Usaco2008 Feb]Making the Grade 路面修整

农夫约翰打算修整农场中一条凹凸不平的土路。按照奶牛们的要求，修整后的路面高度应当单调不下降或单调不上升，即高度上升与高度下降的路段不能同时出现在修整后的道路中。

整条路被分为 $N$ 段，整数序列 $A_1,A_2,\ldots,A_N$ 依次表示各段道路原本的高度。农夫约翰需要确定一个恰好包含 $N$ 个元素的单调不下降或单调不上升序列 $B_1,B_2,\ldots,B_N$ ，作为修整后各段道路的高度。

将任意一段道路垫高或挖低一个单位的花费相同，因此修路的总花费为

|A_1-B_1|+|A_2-B_2|+\cdots+|A_N-B_N|。

请计算将道路修整为高度单调不下降或单调不上升时所需的最小花费。

输入格式

第一行包含一个整数 $N$ ，表示道路的段数。

接下来 $N$ 行，第 $i$ 行包含一个整数 $A_i$ ，表示第 $i$ 段道路原本的高度。

输出一个非负整数，表示将道路修整为高度单调不下降或单调不上升时所需的最小花费。

一种达到最小花费的方案是将各段道路的高度修整为单调不下降序列 $1,2,2,4,5,5,9$ ，总花费为 $3$ 。

本题为 USACO 2008 February 试题「Making the Grade（路面修整）」，题面与测试数据整理自 BZOJ。