Perfect Duet

Sangdeok and Heewon sing together often. One day Sangdeok brought a score that a friend gave him. The score lists the $N$ pitches of the song in order. The two must sing every pitch on the score, and each pitch is sung by exactly one of them. For example, if the score is {3, 6, 2, 5, 4} and Sangdeok sings {3, 2, 4}, then Heewon sings {6, 5}. If Sangdeok sings {6, 2, 5}, then Heewon sings {3, 4}.

Changing pitch in the middle of a song is hard. Singing {4, 6} is harder than singing {4, 4} because the pitch changes. If one person sings $a_1, a_2, \dots, a_k$ in score order, that person's effort is $|a_1 - a_2| + |a_2 - a_3| + \dots + |a_{k-1} - a_k|$. A person who sings one pitch, or none at all, has effort $0$. The effort of the whole score is the sum of the two efforts.

Suppose the score is {1, 3, 8, 12, 13}. If Sangdeok sings the first two pitches and Heewon the last three, Sangdeok's effort is $|1 - 3| = 2$, Heewon's effort is $|8 - 12| + |12 - 13| = 5$, and the sum is $7$. No other division goes below $7$.

Given the score, write a program that finds the minimum effort of dividing it between the two singers.

The first line contains the number of pitches $N$ (1 ≤ $N$ ≤ 2,000).

The second line contains the $N$ pitches, separated by spaces. Each pitch is an integer between 1 and 1,000,000.

Print the minimum effort of singing the score divided between the two people.