题目描述

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

• $B$ 非严格单调，即 $B_1 \le B_2 \le \dots \le B_N$ 或 $B_1 \ge B_2 \ge \dots \ge B_N$。
• 最小化 $S = \sum_{i=1}^N |A_i - B_i|$。

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

输入格式

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

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

输出格式

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

样例

输入样例：

7
1
3
2
4
5
3
9

输出样例：

3

样例解释

序列 $A$：$[1,3,2,4,5,3,9]$

构造非降序列 $B$（或非增）使绝对差和最小。

可以验证 $S$ 的最小值为 $3$。

例如，取 $B = [1,2,2,3,3,3,9]$：

• $|1-1| = 0$
• $|3-2| = 1$
• $|2-2| = 0$
• $|4-3| = 1$
• $|5-3| = 2$
• $|3-3| = 0$
• $|9-9| = 0$

和 $= 4$，不是 $3$。

实际上最优 $B$ 可能是 $[1,2,2,4,5,5,9]$：

• $|1-1|=0$
• $|3-2|=1$
• $|2-2|=0$
• $|4-4|=0$
• $|5-5|=0$
• $|3-5|=2$
• $|9-9|=0$

和 $= 3$。

数据范围

• $1 \le N \le 2000$
• $0 \le A_i \le 10^6$

时空限制

• 时间限制：1 秒
• 空间限制：64 MB

所有题目已整理完毕。