题目描述

$\red{FJ}$打算好好修一下农场中某条凹凸不平的土路。

按奶牛们的要求，修好后的路面高度应当单调上升或单调下降，也就是说，高度上升与高度下降的路段不能同时出现在修好的路中。

整条路被分成了$\red{N}$段，$\red{N}$个整数$\red{A_1, ... , A_N (1 <= N <= 2,000)}$依次描述了每一段路的高度$\red{(0 <= A_i <= 1,000,000,000)}$。

$\red{FJ}$希望找到一个恰好含$\red{N}$个元素的不上升或不下降序列$\red{B_1, ... , B_N，}$作为修过的路中每个路段的高度。由于将每一段路垫高或挖低一个单位的花费相同，修路的总支出可以表示为： $\red{|A_1 - B_1| + |A_2 - B_2| + ... + |A_N - B_N| }$

请你计算一下，$\red{FJ}$在这项工程上的最小支出是多少。$\red{FJ}$向你保证，这个支出不会超过$\red{2^{31}-1}$。

输入格式

第$\red{1}$行: 输入$\red{1}$个整数：$\red{N }$

第$\red{2..N+1}$行: 第$\red{i+1}$行为$\red{1}$个整数：$\red{A_i}$

输出格式

第$\red{1}$行: 输出$\red{1}$个正整数，表示$\red{FJ}$把路修成高度不上升或高度不下降的最小花费

样例

输入样例

7
1
3
2
4
5
3
9

输出样例

3

提示

$\red{FJ}$将第一个高度为$\red{3}$的路段的高度减少为$\red{2，}$

将第二个高度为$\red{3}$的路段的高度增加到$\red{5，}$总花费为$\red{|2-3|+|5-3| = 3，}$

并且各路段的高度为一个不下降序列 $\red{1,2,2,4,5,5,9}$。