题目描述

一条笔直的土路连接着 $FJ$ 农场的两块田地，但它对海拔的变化比 $FJ$ 想要的要大。他的奶牛不介意爬上或爬下一个斜坡，但它们不喜欢交替的山丘和山谷。$FJ$ 希望添加和清除道路上的泥土，使其成为一个单调的斜坡（向上或向下倾斜）。

给你 $N$ 个整数 $A_1 , ... , A_N (1 ≤ N ≤ 2,000)$，描述沿路 $N$ 个等距位置的海拔高度 $(0 ≤ A ≤ 1,000,000,000)$，从第一个田地开始，到另一个田地结束。$FJ$ 希望将这些海拔高度调整为新的序列 $B_1 , ... , B_N$，使得这个序列要么是非递增的，要么是非递减的。由于在沿路任何位置添加或清除污垢的成本相同，因此修改道路的总成本为

$|A_1 - B_1| + |A_2 - B_2| + ... + |A_N - B_N |$

请计算修整这条路使其成为一个连续坡道所需的最小成本。$FJ$ 很高兴地告诉你，使用带符号的 $32$ 位整数肯定可以计算出答案。

输入格式

• 第 $1$ 行: 一个整数: $N$
• 第 $2..N+1$ 行: 第 $i+1$ 行包含一个整数海拔值: $A_i$

输出格式

• 第 $1$ 行: 一个整数，表示 $FJ$ 修整土路使其海拔值为非递增或非递减的最小花费。

样例

7
1
3
2
4
5
3
9

3