给定长度为 $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^6$

输入样例：

7
1
3
2
4
5
3
9

输出样例：

3