Problem Description

Farmer John wants to renovate a road of length $N$. The original elevation of each segment is $A_i$, and after repair it becomes $B_i$, with a cost of $|A_i - B_i|$. We require the repaired road, that is, the sequence $B_i$ you construct, to be monotone nonincreasing or monotone nondecreasing. Find the minimum total cost $\sum_{i=1}^{N} |A_i - B_i|$.

Input Format

The first line contains an integer $N$.

The next $N$ lines each contain an integer $A_i$.

Output Format

Output a single integer, the minimum cost.

7
1
3
2
4
5
3
9

3

Hint

Constraints: $1 \le N \le 2000$, $0 \le A_i \le 10^9$.

Translated by ChatGPT 5