Karaoke

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.

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.

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

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.