Verkefni

Við förum í leik með því að raða hvítum og svörtum go-steinum á borð. Fyrst leggjum við go-stein við vinstri enda borðsins. Næst leggjum við go-stein í $2$. sæti frá vinstri. Með því að endurtaka þetta $n$ sinnum röðum við $n$ go-steinum í eina lárétta röð. Hins vegar, þegar nýr $i$-ti go-steinn er lagður niður, skiptum við út go-steinunum á borðinu samkvæmt eftirfarandi reglum:

• Þegar $i$ er oddatala: Án þess að skipta út go-steinunum sem þegar eru á borðinu er nýi go-steinninn lagður í $i$-ta sæti frá vinstri.
• Þegar $i$ er slétt tala: Ef liturinn á nýja go-steininum sem lagður er í $i$-ta sæti frá vinstri er sá sami og liturinn á go-steininum lengst til hægri á borðinu, þá er nýi go-steinninn lagður í $i$-ta sæti frá vinstri án þess að skipta út go-steinunum á borðinu. Annars, það er að segja ef liturinn á nýja go-steininum í $i$-ta sæti frá vinstri er ólíkur litnum á go-steininum lengst til hægri á borðinu, þá fjarlægjum við fyrst alla samliggjandi go-steina af sama lit við hægri enda borðsins og skiptum þeim út fyrir go-steina af sama lit og $i$-ti go-steinninn. Síðan leggjum við $i$-ta go-steininn við hægri enda borðsins.

Til dæmis, gerum ráð fyrir að eftir að fyrstu $7$ go-steinarnir hafa verið lagðir niður sé staðan:

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

(þar sem $\circ$ táknar hvítan go-stein en $\bullet$ táknar svartan go-stein).

• Ef $8$. go-steinninn er hvítur ($\circ$), þá er hann lagður niður óbreyttur þar sem hann hefur sama lit og steinninn lengst til hægri. Því verða go-steinarnir á borðinu:

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

• Ef $8$. go-steinninn er svartur ($\bullet$), þá er litur hans ólíkur steininum lengst til hægri ($\circ$), svo við fjarlægjum fyrst $3$ samliggjandi hvíta go-steina ($\circ$) við hægri enda borðsins og skiptum þeim út fyrir svarta go-steina ($\bullet$). Síðan leggjum við $8$. go-steininn við hægri endann. Því verða go-steinarnir á borðinu:

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

Þegar röð go-steinanna sem leggja á niður er gefin sem inntak, skrifið forrit sem finnur fjölda hvítra go-steina á borðinu eftir að búið er að raða öllum $n$ go-steinunum.

Inntak

Á $1$. línu er jákvæð heiltala $n$ ($1 \le n \le 100\,000$). Frá og með $2$. línu er á $i+1$-tu línu ($1 \le i \le n$) heiltala $c_{i}$ sem táknar lit $i$-ta go-steinsins sem lagður er niður, þar sem $c_{i}$ jafnt og $0$ táknar að $i$-ti go-steinninn sé hvítur, en $1$ táknar að $i$-ti go-steinninn sé svartur.

Af prófunargögnunum uppfylla $50\%$ stiganna skilyrðið $n \le 10\,000$.

Úttak

Prentið $1$ línu sem inniheldur eingöngu fjölda hvítra go-steina á borðinu eftir að búið er að raða öllum $n$ go-steinunum.

Dæmi um inntak og úttak

Inntaksdæmi 1

8
1
0
1
1
0
0
0
0

Úttaksdæmi 1

6

Inntaksdæmi 2

8
1
0
1
1
0
0
0
1

Úttaksdæmi 2

2