Kule

Limit pamięci: 32 MB

Na okręgu umieszczono pudełek ponumerowanych zgodnie z ruchem wskazówek zegara od do , gdzie . W pudełkach znajdują się kule, przy czym łącznie we wszystkich pudełkach jest ich nie więcej niż . Należy przełożyć kule w taki sposób, żeby w każdym pudełku pozostała co najwyżej jedna kula. W jednym ruchu można przełożyć jedną kulę z pudełka, w którym się znajduje, do pudełka sąsiedniego.

Zadanie

Ułóż program, który:

• wczytuje ze standardowego wejścia liczbę pudełek i rozmieszczenie kul w pudełkach,
• oblicza minimalną liczbę ruchów, jakie trzeba wykonać, aby w każdym pudełku była co najwyżej jedna kula,
• zapisuje tę liczbę na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia jest zapisana jedna liczba całkowita dodatnia. Jest to liczba pudełek . W każdym z kolejnych wierszy jest zapisana jedna liczba całkowita nieujemna. W -tym z tych wierszy jest zapisana liczba kul w -tym pudełku.

Wyjście

Na standardowe wyjście należy zapisać jedną liczbę całkowitą nieujemną tj. minimalną liczbę ruchów, jakie trzeba wykonać, aby w każdym pudełku była co najwyżej jedna kula.

Przykład

Dla danych wejściowych:

12
0
0
2
4
3
1
0
0
0
0
0
1

poprawną odpowiedzią jest:

19

Autor zadania: Krzysztof Diks.