Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_22_06 - Podzial

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 = |a1 - a2| + |a2 - a3| + ... + |an - 1 - an|

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 106 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.


Dodane przez:Maciej Boniecki
Data dodania:2015-04-25
Limit czasu wykonania programu:0.200s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU JS-MONKEY
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.