8586번 - Zapałki 다국어

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ę.

Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą $n$ ($1 ≤ n ≤ 1\,000\,000$) oznaczającą liczbę zapałek Bajtka. Drugi wiersz opisuje ułożenie kolejnych zapałek - zawiera ciąg $n$ liczb całkowitych $x_1, x_2, \dots , x_n$, przy czym $x_i$ oznacza zwrot $i$-tej zapałki w ciągu: $0$ jeśli główka zapałki znajduje się z lewej strony, zaś $1$ jeśli główka zapałki znajduje się z prawej strony.

Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać jedną liczbę całkowitą równą minimalnej liczbie zapałek, jakie należy odwrócić.