Make a Monotone Sequence

Time limit2sMemory limit128 MB

Summary

Given N nonnegative integers, build a monotone (non-decreasing or non-increasing) sequence minimizing the total absolute difference from the original.

Level: Hard8 of 10
Topics: Dynamic programming, Greedy, Heap, Math
Solved: No attempts yet

Problem

You are given a sequence $A_1, A_2, \dots, A_N$ of $N$ nonnegative integers. Choose a sequence $B_1, B_2, \dots, B_N$ to minimize $|A_1-B_1| + |A_2-B_2| + \dots + |A_N-B_N|$ .

The sequence $B$ must be monotone. That means it must satisfy either $B_1 \le B_2 \le \dots \le B_N$ or $B_1 \ge B_2 \ge \dots \ge B_N$ .

Input

The first line contains the length $N$ of the sequence. Each of the next $N$ lines contains one value of $A_1, A_2, \dots, A_N$ in order.

Output

Print the minimum possible sum of absolute differences.

Constraints

$1 \le N \le 2\,000$
$0 \le A_i \le 1\,000\,000\,000$

Examples1

Example 1
Input
```
7
1
3
2
4
5
3
9
```
Expected output
```
3
```