Make a Monotone Sequence

Time limit2s

Memory limit128 MB

Problem

Input

Output

Constraints

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$.

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.

Print the minimum possible sum of absolute differences.