Description

一条笔直的道路连接着约翰农场的两块田地，但它变化的海拔高度超出了约翰的想象。约翰希望添加或清除道路上的泥土，使其成为一个单调的斜坡（向上或向下倾斜）。给定$N$个整数$A_1,…,A_N（0≤A i≤10^8，1≤N≤2000）$，用于描述道路上$N$个等距位置的海拔高度。将这些海拔高度调整为新的非递增或非递减序列$B_1,…,B_ N$。由于在道路沿线的任何位置添加或清除泥土的费用都相同，因此修改道路的总费用为$|A_1-B_1|+|A_2-B_2|+…+|A_N-B_N|$，请计算道路修整的最小成本，答案为不大于$32$位的整数。

Format

Input

第$1$行输入单个整数$N$；接下来的$N$行，每行都包含一个整数$A_i$，表示海拔高度。

Output

输出对道路进行坡度调整的最小成本，使其在海拔高度上非递增或非递减。

Samples

7
1
3
2
4
5
3
9

3

来源

POJ3666