题目描述

约翰打算好好修一下农场中某条凹凸不平的土路。按奶牛们的要求，修好后的路面高度应当单调上升或单调下降，也就是说，高度上升与高度下降的路段不能同时出现在修好的路中。整条路被分成了 $N$ 段，$N$ 个整数 $A_1, A_2, ..., A_N(1≤N≤2000, 0≤A_i≤10^9)$ 依次描述了每一段路的高度。约翰希望找到一个恰好含 $N$ 个元素的不上升或不下降序列 $B_1, B_2, ..., B_N$，作为修过的路中每个路段的高度。由于将每一段路垫高或挖低一个单位的花费相同，修路的总支出可以表示为:

请你计算一下，约翰在这项工程上的最小支出是多少.约翰向你保证，这个支出不会超过 $2^{31} - 1$.

输入输出格式

输入

第1行输入1个整数 $N$，接下来 $N$ 行输入 $A_i$。

输出

输出1个正整数，表示约翰把路修成高度不上升或高度不下降的最小花费。

样例

输入1

7
1
3
2
4
5
3
9

输出1

3

时间及空间限制

1s, 256MB. 题目来源：USACO2008FEB, 金组 T1

提示

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