1393: Alien 的数列

内存限制:512 MB 时间限制:1.000 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:84 通过:29

题目描述

Alien 们很迷信,所以对于一个数列,它们如果觉得它不吉利,就要将这个数列进行处理,但处理方式很诡异。
对于一个数列 A1, A2, A3 ... AN,如果它不是不下降的,那么 Alien们就认为这个是不吉利的。Alien 们要尽力把不吉利的数列修改成为吉利的,可以把这个数列的中的某个数修改为 New,代价是|Ai-New|。
现在它们委托你帮忙修改一下, 你的目的是将它们给出的一个数列改成不下降的,而且代价最小。

输入格式

第一行一个整数 N。
接下来 N 行,每行一个数,表示 Alien 们给出的原数列。

输出格式

输出一行一个数 Ret,表示最小代价。

输入样例 复制

5
3
2
-1
2
11

输出样例 复制

4

数据范围与提示

样例解释:
修改成 2 2 2 2 11,代价是 1+3=4
数据范围:
对于 30%数据 N≤100, |Ai|≤8000
对于 100%数据 N≤5000, |Ai|≤10^9