Szklanki

Limit pamięci: 64 MB

Bitoasia ustawiła pewną liczbę szklanek w rzędzie i do każdej nalała tyle samo wody, następnie wyszła do łazienki. W tym czasie do pokoju ze szklankami przyszedł Bajtokozik i postanowił zrobić Bitoasi psikusa - szybko poprzelewał wodę między szklankami.

Gdy Bitoasia wróciła i zobaczyła, że w szklankach jest nierównomierna ilość wody, to bardzo się zdenerwowała i pobiegła rozpłakana do Bitomamy. Jednak, po przeprowadzeniu dochodzenia, Bitomama Bitoasi nie znalazła sprawcy. Nie pozostało więc nic innego, jak przelać wodą ze szklanek tak, aby w każdej była taka sama ilość wody.

Bitoasia chce wykonać jak najmniejszą liczbę ruchów, aby zbytnio się nie zmęczyć. Pojedynczy ruch polega na wzięciu dowolnej szklanki i przelaniu wody do szklanki sąsiedniej (z lewej bądź prawej strony). Stwierdź, ile minimalnie ruchów musi wykonać Bitoasia.

Zakładamy, że pojedyncza szklanka może pomieścić całą wodę ze wszystkich szklanek. Wiemy, że na początku w każdej szklance była równomierna ilość wody, której liczba jednostek była liczbą całkowitą. Bajtokozik podczas przelewania nie wylał żadnej kropli poza szklankę oraz żadna kropla nie wyparowała.

Wejście

Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą (), oznaczającą liczbę szklanek ustawionych w rzędzie. Następny wiersz wejścia zawiera liczb całkowitych (), gdzie oznacza liczbę jednostek wody znajdującej się w -tej szklance (po psikusie Bajtokozika).

Wyjście

Pierwszy wiersz standardowego wyjścia powinien zawierać jedną liczbę całkowitą, równą minimalnej liczbie ruchów, jakie może wykonać Bitoasia.

Przykład

Dla danych wejściowych:

4
3 1 3 5

poprawną odpowiedzią jest:

2

Autor zadania: Jacek Tomasiewicz.