「Making the Grade」 分级

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

1、B非严格单调，即$B_1 \le B_2 \le \dots \le B_N$或$B_1 \ge B_2 \ge \dots \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 可能含有视频讲解