8694번 - Szklanki 다국어

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.

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

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