Tehtävä

Pelaamme peliä asettelemalla valkoisia ja mustia go-kiviä pöydälle. Ensin asetamme go-kiven pöydän vasempaan päähän. Seuraavaksi asetamme go-kiven $2$. paikalle vasemmalta. Toistamalla tätä $n$ kertaa asetamme $n$ go-kiveä yhteen vaakasuoraan riviin. Kun asetamme uuden $i$-nnen go-kiven, korvaamme pöydällä olevia go-kiviä seuraavien sääntöjen mukaisesti:

• Kun $i$ on pariton: Pöydällä jo olevia go-kiviä ei korvata, vaan uusi go-kivi asetetaan $i$-nnelle paikalle vasemmalta.
• Kun $i$ on parillinen: Jos vasemmalta $i$-nnelle paikalle asetettavan uuden go-kiven väri on sama kuin pöydän oikeassa reunassa olevan go-kiven väri, pöydällä olevia go-kiviä ei korvata, vaan uusi go-kivi asetetaan $i$-nnelle paikalle vasemmalta. Muussa tapauksessa, eli jos vasemmalta $i$-nnelle paikalle asetettavan uuden go-kiven väri eroaa pöydän oikeassa reunassa olevan go-kiven väristä, poistetaan ensin kaikki pöydän oikeassa päässä peräkkäin olevat samanväriset go-kivet ja korvataan ne $i$-nnen go-kiven värisillä go-kivillä. Sen jälkeen $i$-s go-kivi asetetaan pöydän oikeaan päähän.

Oletetaan esimerkiksi, että kun ensimmäiset $7$ go-kiveä on asetettu, tilanne on:

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

(missä $\circ$ tarkoittaa valkoista go-kiveä ja $\bullet$ tarkoittaa mustaa go-kiveä).

• Jos $8$. go-kivi on valkoinen ($\circ$), se on samanvärinen kuin oikeanpuoleisin go-kivi, joten se asetetaan paikalleen sellaisenaan. Tällöin pöydällä olevat go-kivet ovat:

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

• Jos $8$. go-kivi on musta ($\bullet$), sen väri eroaa oikeanpuoleisimmasta go-kivestä ($\circ$), joten ensin poistetaan pöydän oikeassa päässä olevat $3$ peräkkäistä valkoista go-kiveä ($\circ$) ja korvataan ne mustilla go-kivillä ($\bullet$). Sitten oikeaan päähän asetetaan $8$. go-kivi. Tällöin pöydällä olevat go-kivet ovat:

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

Kun syötteenä annetaan asetettavien go-kivien järjestys, kirjoita ohjelma, joka laskee pöydällä olevien valkoisten go-kivien lukumäärän sen jälkeen, kun kaikki $n$ go-kiveä on asetettu.

Syöte

$1$. rivillä on positiivinen kokonaisluku $n$ ($1 \le n \le 100\,000$). $2$. rivistä alkaen rivillä $i+1$ ($1 \le i \le n$) on kokonaisluku $c_{i}$, joka ilmaisee $i$-ntenä asetettavan go-kiven värin: jos $c_{i}$ on $0$, $i$-s go-kivi on valkoinen, ja jos se on $1$, $i$-s go-kivi on musta.

Arvosteluaineistosta $50\%$ pisteistä täyttää ehdon $n \le 10\,000$.

Tuloste

Tulosta $1$ rivi, joka sisältää vain pöydällä olevien valkoisten go-kivien lukumäärän sen jälkeen, kun kaikki $n$ go-kiveä on asetettu.

Esimerkkisyötteet ja -tulosteet

Esimerkkisyöte 1

8
1
0
1
1
0
0
0
0

Esimerkkituloste 1

6

Esimerkkisyöte 2

8
1
0
1
1
0
0
0
1

Esimerkkituloste 2

2