题目描述

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

1、$\red {B}$非严格单调，即$\red {B _1~ ≤B _2~ ≤…≤B_N~}$或$\red {B _1~ ≥B _2~ ≥…≥B_N~}$。

2、最小化$\red { S=\sum_ {i=1} ^N|A _i −B _i |}$。

只需要求出这个最小值$\red {S}$。

输入格式

第一行包含一个整数$\red {N}$。

接下来$\red {N}$行，每行包含一个整数$\red {A_i~}$。

输出格式

输出一个整数，表示最小$\red {S}$值。

样例

输入样例

7
1
3
2
4
5
3
9

输出样例

3

提示

$\red {1≤N≤2000}$,

$\red {0≤A _i~ ≤10^9}$