Zapałki
Limit pamięci: 32 MB
Bajtek bawi się zapałkami.
Na jednym z końców zapałki znajduje się główka pokryta masą ułatwiającą zapłon.
Bajtek ułożył zapałki w linii prostej jedna obok drugiej, w taki sposób, że każdy koniec zapałki
sąsiaduje z końcem pewnej innej zapałki, oprócz dwóch skrajnych zapałek, które
sąsiadują tylko jednym końcem.
Przykładowe ułożenie zapałek.
Bajtek chciałby podpalić pierwszą zapałkę (skrajną z lewej)
tak aby wszystkie zapałki spaliły się. Pierwszą zapałkę zapali on przy użyciu zapalniczki, może więc
to zrobić bez względu na jej ułożenie. Natomiast między kolejnymi zapałkami ogień przeniesie się tylko,
jeśli co najmniej jedna z tych zapałek w miejscu połączenia będzie zwrócona główką.
Zastanawiamy się, ile minimalnie zapałek musimy odwrócić, aby wszystkie zapałki spaliły się, jeśli podpalimy pierwszą zapałkę.
Wejście
Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą () oznaczającą liczbę zapałek Bajtka.
Drugi wiersz opisuje ułożenie kolejnych zapałek - zawiera ciąg liczb całkowitych
, przy czym oznacza zwrot -tej zapałki w ciągu:
jeśli główka zapałki znajduje się z lewej strony, zaś jeśli główka zapałki znajduje się
z prawej strony.
W testach wartych łącznie co najmniej 50% punktów zachodzi dodatkowo warunek .
Wyjście
Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać jedną liczbę całkowitą równą minimalnej
liczbie zapałek, jakie należy odwrócić.
Przykład
Dla danych wejściowych:
5
1 0 0 1 1
poprawną odpowiedzią jest:
2
Autor zadania: Jacek Tomasiewicz.