Modify Array

Find the minimum total absolute modification cost to turn the array into a non-decreasing or a non-increasing sequence; each position may be changed to any integer value, at a cost equal to the absolute difference between the new and old values.

输入格式

The first line contains n; the second line contains n integers. The original constraints are 1≤n≤1000 and 1≤arr[i]≤10^9; this site widens the value range to 0..10^9 to keep the 0 in the third source example.

输出格式

Output the minimum total modification cost over the two directions, as a 64-bit non-negative integer.

样例 1

输入：

6
9 8 7 2 3 3

输出：

1

样例 2

输入：

5
1 2 3 3 4

输出：

0

样例 3

输入：

7
0 1 2 5 6 5 7

输出：

1