POLSKI SPOJ

Grześ i Staś wypisali sobie na kartce ciąg składający się z n liczb. Chłopcy zdefiniowali wartość tego ciągu jako sumę wartości bezwzględnych różnic kolejnych jego elementów:

W = |a₁ - a₂| + |a₂ - a₃| + ... + |a_{n - 1} - a_n|

Teraz Grześ i Staś zastanawiają się czy mogliby uzyskać mniejszą wartość, gdyby podzielili elementy na dwa ciągi, zachowując ich kolejność. Twoim zadaniem jest wyznaczenie minimalnej sumy wartości tych dwóch ciągów.

Wejście

W pierwszej linii wejścia znajduje się jedna liczba całkowita n ∈ [2;1000] określająca liczbę elementów ciągu.

W kolejnej linii znajduje się n liczb całkowitych z zakresu od 1 do 10⁶ będących wartościami kolejnych elementów ciągu.

Wyjście

Na wyjściu należy wypisać minimalną sumę wartości nowo powstałych ciągów.

Przykład

Wejście

6
1 9 2 10 3 11

Wyjście

4

Wyjaśnienie do przykładu

Sumę wartości równą 4 możemy uzyskać tworząc ciągi: 1 2 3 oraz 9 10 11.