cho.sh
Notes
Loading...

Make a Monotone Sequence

Time limit

2s

Memory limit

128 MB

Problem

You are given a sequence A1,A2,…,ANA_1, A_2, \dots, A_NA1​,A2​,…,AN​ of NNN nonnegative integers. Choose a sequence B1,B2,…,BNB_1, B_2, \dots, B_NB1​,B2​,…,BN​ to minimize ∣A1−B1∣+∣A2−B2∣+⋯+∣AN−BN∣|A_1-B_1| + |A_2-B_2| + \dots + |A_N-B_N|∣A1​−B1​∣+∣A2​−B2​∣+⋯+∣AN​−BN​∣.

The sequence BBB must be monotone. That means it must satisfy either B1≤B2≤⋯≤BNB_1 \le B_2 \le \dots \le B_NB1​≤B2​≤⋯≤BN​ or B1≥B2≥⋯≥BNB_1 \ge B_2 \ge \dots \ge B_NB1​≥B2​≥⋯≥BN​.

Input

The first line contains the length NNN of the sequence. Each of the next NNN lines contains one value of A1,A2,…,ANA_1, A_2, \dots, A_NA1​,A2​,…,AN​ in order.

Output

Print the minimum possible sum of absolute differences.

Constraints

  • 1≤N≤2 0001 \le N \le 2\,0001≤N≤2000
  • 0≤Ai≤1 000 000 0000 \le A_i \le 1\,000\,000\,0000≤Ai​≤1000000000