You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

农夫约翰想改造一条长度为 $N$ 的路，原来的路的每一段海拔是 $A_i$，修理后是 $B_i$，花费 $|A_i - B_i|$。我们要求修好的路，即你构造的 $B_i$，是单调不升或者单调不降的。求最小花费 $\sum_{i=1}^{N} |A_i - B_i|$。

输入格式

第一行包含一个整数 $N$。

接下来 $N$ 行，每行包含一个整数 $A_i$。

输出格式

一行一个整数，表示最小花费。

7
1
3
2
4
5
3
9

3

提示

数据范围为 $1\le N\le 2000, 0\le A_i\le 10^9$。