Karaoke

Interview

Time limit2sMemory limit512 MB

Summary

Assign each note of a sequence to one of two singers so that the total of the absolute pitch jumps within each singer's subsequence is minimized.

Level: Medium7 of 10
Topics: Dynamic programming, Array, Math, Implementation
Solved: No attempts yet

Problem

Yeongseon and Hyobin split one song between them at a karaoke room.

Pitches are integers from 1 to 1,000,000, where 1 is the lowest pitch and 1,000,000 is the highest. Both singers can sing every pitch in tune.

A song is a sequence of notes, and each note is sung by exactly one of the two singers.

The difficulty a singer feels is the sum of the pitch differences between consecutive notes that this singer sang, taken in singing order. For example, if Yeongseon sang 8, 8, 13, 12, the difficulty is $|8-8| + |13-8| + |12-13| = 0 + 5 + 1 = 6$ . A singer who sang one note, and a singer who sang no note at all, feels difficulty 0.

Write a program that divides the notes so that the sum of the two difficulties is as small as possible, and prints that minimum sum.

Input

The first line contains the number of notes in the song, $N$ ( $1 \le N \le 2000$ ).

The second line contains the $N$ notes of the song in singing order. Each pitch is an integer between 1 and 1,000,000.

Output

Print the minimum possible sum of the two difficulties on the first line.

Hint

In the first example the minimum is reached when Yeongseon sings the first two notes and Hyobin sings the last three. In the second example the minimum is reached when the notes are sung in the order Yeongseon, Hyobin, Hyobin, Yeongseon, Yeongseon.

Examples3

Example 1
Input
```
5
1 3 8 12 13
```
Expected output
```
7
```
Example 2
Input
```
5
1 5 6 2 1
```
Expected output
```
3
```
Example 3
Input
```
8
5 5 5 5 4 4 4 4
```
Expected output
```
0
```