Monotonic Road Grading

Farmer John has a straight dirt road connecting two fields on his farm. The road has varying elevations given by a sequence of integers \(A_1, A_2, \dots, A_N\). He wishes to modify the road so that the new sequence \(B_1, B_2, \dots, B_N\) is monotonic (either nondecreasing or nonincreasing). The cost to change the elevation at any position is \(|A_i - B_i|\), and the total cost is \(\sum_{i=1}^N |A_i - B_i|\). Your task is to compute the minimum total cost needed to achieve such a modification.

Input constraints:

• \(1 \le N \le 2000\)
• \(0 \le A_i \le 10^9\)

You may assume that signed 32-bit integers are sufficient for computing the answer.

Mathematical Formulation:

Given a sequence \(A_1, A_2, \dots, A_N\), find a sequence \(B_1, B_2, \dots, B_N\) such that either \[ B_1 \le B_2 \le \cdots \le B_N \quad \text{or} \quad B_1 \ge B_2 \ge \cdots \ge B_N, \] minimizing the cost \[ \sum_{i=1}^{N} |A_i - B_i|. \]

inputFormat

The first line of input contains a single integer \(N\), the number of positions along the road.

The second line contains \(N\) space-separated integers: \(A_1, A_2, \dots, A_N\), representing the elevations.

outputFormat

Output a single integer, the minimum total cost of modifying the road so that it becomes a continuous monotonic slope.

sample

5
1 2 3 2 1

2