Łańcuch

Limit pamięci: 32 MB

Bajtocja nie zawsze była państwem demokratycznym. W jej historii były również czarne karty. Pewnego razu, generał Bajtelski - przywódca junty żelazną ręką rządzącej Bajtocją - postanowił zakończyć stan wojenny, trwający od momentu przejęcia władzy, i zwolnić więzionych działaczy opozycji. Nie chciał jednak uwolnić przywódcy opozycji Bajtazara. Postanowił przykuć go do murów więzienia za pomocą bajtockiego łańcucha. Bajtocki łańcuch składa się z połączonych ze sobą ogniw oraz przymocowanego do muru pręta. Choć ogniwa nie są połączone z prętem, to bardzo trudno jest je z niego zdjąć. - Generale, czemuś mnie przykuł do murów więzienia, miast uwolnić, jako to uczyniłeś z moimi kamratami! - wołał Bajtazar. - Ależ Bajtazarze, wszak nie jesteś przykuty i z pewnością potrafisz sam zdjąć trzymające Cię ogniwa z pręta wystającego z murów więzienia. - przewrotnie stwierdził generał Bajtelski, po czym dodał - Uporaj się z tym jednak przed godziną cyfracyjną i nie dzwoń łańcuchami po nocy, gdyż w przeciwnym przypadku będę zmuszony wezwać funkcjonariuszy Cyfronicji Obywatelskiej. Pomóż Bajtazarowi!

Ponumerujmy kolejne ogniwa łańcucha liczbami . Ogniwa te możemy zakładać i zdejmować z pręta zgodnie z następującymi zasadami:

• jednym ruchem możemy zdjąć lub założyć na pręt tylko jedno ogniwo,
• ogniwo nr 1 można zawsze zdjąć lub założyć na pręt,
• jeżeli ogniwa o numerach (dla ) są zdjęte z pręta, a ogniwo nr jest założone, to możemy zdjąć lub założyć ogniwo nr .

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia opis bajtockiego łańcucha,
• obliczy minimalną liczbę ruchów, które należy wykonać, aby zdjąć wszystkie ogniwa bajtockiego łańcucha z pręta,
• wypisze wynik na standardowe wyjście1.

Wejście

W pierwszym wierszu standardowego wejścia zapisano jedną dodatnią liczbę całkowitą , . W drugim wierszu zapisano liczb całkowitych pooddzielanych pojedynczymi odstępami. Jeśli , to ogniwo nr jest założone na pręt, a jeśli , to jest z niego zdjęte.

Wyjście

Pierwszy wiersz standardowego wejścia powinien zawierać jedną liczbę całkowitą, równą minimalnej liczbie ruchów potrzebnych do zdjęcia wszystkich ogniw bajtockiego łańcucha z pręta.

Przykład

Dla danych wejściowych:

4
1 0 1 0

poprawną odpowiedzią jest:

6

Autor zadania: Marcin Kubica.