Basen

Piotrek jest ratownikiem na basenie. Ponieważ praca jest strasznie nudna (rzadko zdarza mu się interweniować), wymyślił sobie dodatkowe zajęcie: rozdzielanie ludzi pomiędzy tory pływackie.

Basen podzielony jest na N torów. Łącznie pływa w nim obecnie S ludzi. Według Piotrka, najlepiej byłoby, gdyby byli mniej-więcej równo rozłożeni pomiędzy poszczególne tory, jednak nie jest to takie proste do osiągnięcia. W takim razie Piotrek póki co zadowoli się trochę słabszym rezultatem: chciałby, aby liczby pływających ludzi na każdych dwóch sąsiednich torach różniły się o co najwyżej 1.

Aby to osiągnąć Piotrek musi przemieścić ludzi. Jedynym poleceniem, które może wydać, jest nakazanie jednej osobie zmiany toru na sąsiedni po lewej, albo prawej (Piotrek precyzuje który z tych dwóch). Jedna osoba może dostać, w razie potrzeby, więcej takich nakazów po kolei. Ile co najmniej poleceń musi wydać Piotrek, aby spełnić swoje założenia?

Wejście

W pierwszym wierszu standardowego wejścia znajduje się liczba całkowita n (1 <= n <= 400). Drugi wiersz zawiera n liczb całkowitych nieujemnych t_i -- liczby pływaków na poszczególnych torach. Wiadomo, że S = t_1 + t_2 + ... + t_n <= 1500.

Wyjście

Na standardowe wyjście Twój program powinien wypisać jedną liczbę p - minimalną liczbę poleceń wydanych przez Piotrka.

Przykład

Dla danych wejściowych:

3
8 0 2

poprawnym wynikiem jest:
5