题目描述

给定长度为 𝑁 的序列 𝐴，构造一个长度为𝑁 的序列 𝐵，满足：

1. 𝐵 非严格单调，即 $𝐵_1≤𝐵_2≤…≤𝐵_𝑁$ 或 $𝐵_1≥𝐵_2≥…≥𝐵_𝑁$。
2. 最小化 $𝑆=∑_{𝑖=1}^{𝑁}|𝐴_𝑖−𝐵_𝑖|$。

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

输入格式

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

接下来$𝑁$行，每行包含一个整数 $𝐴_𝑖$。

输出格式

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

数据范围

$1≤𝑁≤2000,0≤𝐴_𝑖≤10^6$

输入样例：

7
1
3
2
4
5
3
9

3