Zadanie

Gramy w grę polegającą na układaniu białych i czarnych kamieni go na stole. Najpierw kładziemy kamień go na lewym końcu stołu. Następnie kładziemy kamień go na $2$-gim miejscu od lewej. Powtarzając to $n$ razy, układamy $n$ kamieni go w jednym poziomym rzędzie. Jednak podczas dokładania nowego $i$-tego kamienia go zamieniamy kamienie na stole według następujących zasad:

• Gdy $i$ jest nieparzyste: nie zamieniając kamieni leżących już na stole, kładziemy nowy kamień na $i$-tym miejscu od lewej.
• Gdy $i$ jest parzyste: jeśli kolor nowego kamienia kładzionego na $i$-tym miejscu od lewej jest taki sam jak kolor skrajnie prawego kamienia na stole, to nie zamieniamy kamieni na stole i kładziemy nowy kamień na $i$-tym miejscu od lewej. W przeciwnym razie, to znaczy gdy kolor nowego kamienia kładzionego na $i$-tym miejscu od lewej różni się od koloru skrajnie prawego kamienia na stole, najpierw zdejmujemy wszystkie kolejne kamienie tego samego koloru znajdujące się na prawym końcu stołu i zastępujemy je kamieniami tego samego koloru co $i$-ty kamień. Następnie kładziemy $i$-ty kamień na prawym końcu stołu.

Na przykład załóżmy, że po położeniu pierwszych $7$ kamieni go stan na stole wygląda następująco:

$$\circ \circ \bullet \bullet \circ \circ \circ$$

(gdzie $\circ$ oznacza biały kamień go, a $\bullet$ oznacza czarny kamień go).

• Jeśli $8$-my kamień jest biały ($\circ$), to ponieważ ma ten sam kolor co kamień na prawym końcu, kładziemy go bez zmian. Wobec tego kamienie na stole będą wyglądać następująco:

$$\circ \circ \bullet \bullet \circ \circ \circ \circ$$

• Jeśli $8$-my kamień jest czarny ($\bullet$), to ponieważ ma inny kolor niż kamień na prawym końcu ($\circ$), najpierw zdejmujemy $3$ kolejne białe kamienie ($\circ$) z prawego końca stołu i zastępujemy je czarnymi kamieniami ($\bullet$). Następnie na prawym końcu kładziemy $8$-my kamień. Wobec tego kamienie na stole będą wyglądać następująco:

$$\circ \circ \bullet \bullet \bullet \bullet \bullet \bullet$$

Mając daną na wejściu kolejność dokładanych kamieni go, napisz program, który obliczy liczbę białych kamieni go leżących na stole po ułożeniu wszystkich $n$ kamieni.

Wejście

W $1$-szym wierszu zapisana jest dodatnia liczba całkowita $n$ ($1 \le n \le 100\,000$). Począwszy od $2$-giego wiersza, w $i+1$-szym wierszu ($1 \le i \le n$) zapisana jest liczba całkowita $c_{i}$ określająca kolor $i$-tego dokładanego kamienia go: $c_{i}$ równe $0$ oznacza, że $i$-ty kamień jest biały, natomiast $1$ oznacza, że $i$-ty kamień jest czarny.

Spośród danych testowych, dla $50\%$ punktów zachodzi $n \le 10\,000$.

Wyjście

Wypisz $1$ wiersz zawierający wyłącznie liczbę białych kamieni go leżących na stole po ułożeniu wszystkich $n$ kamieni.

Przykłady wejścia i wyjścia

Przykład wejścia 1

8
1
0
1
1
0
0
0
0

Przykład wyjścia 1

6

Przykład wejścia 2

8
1
0
1
1
0
0
0
1

Przykład wyjścia 2

2