[中山市选2011] 序列
时间限制：10s 空间限制：128MB
题目描述
小 W 很喜欢序列，尤其喜欢“W”形的和“M”形的序列。定义“M”形
的序列为一个长度为 T 的序列{Si}，满足：存在 1 < x < y < z < N，使得S1 < ... <
Sx > ... > Sy < ... < Sz > ... > ST。
一天他看到了一个长度为N 的整数序列{Ai}，他想通过一些修改把序列变成
“M”形的。但这时小 X 过来了，说这个序列是他的，小 W 如果想要修改就要
支付一定的费用。每支付一单位的费用，小 W 都可以进行这样的操作：将一段
连续的数同时加上 1，即选定i, j 满足1 ≤ i ≤ j ≤ N 并令Ai, Ai+1, ..., Aj均加上1。
小 W 想用最小的费用将序列变成“M”形的。但是有个条件：如果他修改
成的目标是序列{Bi}满足B1 < ... < Bx > ... > By < ... < Bz > ... > BN， 那么必须有Ay=
By。
现在，他希望你来帮他计算最小费用。
输入格式
第一行包含一个整数 N，表示序列A的长度。
第二行有 N 个整数给出初始的序列{Ai}。
输出格式
仅包含一行，为最小的花费。
样例输入
5 2 1 2 2 3
样例输出
4
提示
对于100%的数据满足 5 ≤ N ≤ 100 000，0 ≤ Ai ≤ 10 ^9。
题目来源
没有写明来源