题目描述

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

1、B非严格单调，即$B\_1 \le B\_2 \le … \le B\_N$或$B\_1 \ge B\_2 \ge … \ge B\_N$。
2、最小化 $S = \sum\_{i=1}^N|A\_i-B\_i|$。

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

输入格式

第一行包含一个整数N。

接下来N行，每行包含一个整数$A\_i$。

输出格式

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

数据范围

$1 \le N \le 2000$,
$0 \le A\_i \le 10^9$

输入样例：

7
1
3
2
4
5
3
9

输出样例：

3

来源

• 《算法竞赛进阶指南》
• acwing 可能含有视频讲解