题目描述

给定长度为 $N$ 的序列$A$，构造一个长度为$N$ 的序列$B$，满足：

1. $B$非严格单调，即 $B_1≤B_2≤…≤B_N$或 $B_1≥B_2≥…≥B_N$。
2. 最小化$s=\displaystyle\sum_{i=1}^{N}|A_i−B_i|$。

只需要求出这个最小值 $S$。

输入格式

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

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

输出格式

输出一个整数，表示最小 $S$值。

样例

7
1
3
2
4
5
3
9

3

数据范围

$1≤N≤2000, 0≤A_i≤10^6$

来源

• POJ3666
• 算法竞赛进阶指南