Oppgave

Vi spiller et spill ved å legge hvite og svarte go-steiner på et bord. Først legger vi en go-stein ved venstre ende av bordet. Deretter legger vi en go-stein på den $2$. plassen fra venstre. Ved å gjenta dette $n$ ganger stiller vi opp $n$ go-steiner i én horisontal rekke. Men når vi legger en ny $i$-te go-stein, bytter vi ut go-steinene på bordet etter følgende regler:

• Når $i$ er oddetall: Uten å bytte ut go-steinene som allerede ligger på bordet, legger vi den nye go-steinen på den $i$-te plassen fra venstre.
• Når $i$ er partall: Hvis fargen på den nye go-steinen som legges på den $i$-te plassen fra venstre er den samme som fargen på go-steinen lengst til høyre på bordet, legger vi den nye go-steinen på den $i$-te plassen fra venstre uten å bytte ut go-steinene på bordet. Ellers, det vil si hvis fargen på den nye go-steinen på den $i$-te plassen fra venstre er ulik fargen på go-steinen lengst til høyre på bordet, fjerner vi først alle sammenhengende go-steiner av samme farge ved høyre ende av bordet og erstatter dem med go-steiner av samme farge som den $i$-te go-steinen. Deretter legger vi den $i$-te go-steinen ved høyre ende av bordet.

Anta for eksempel at tilstanden etter at de første $7$ go-steinene er lagt, er:

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

(der $\circ$ representerer en hvit go-stein og $\bullet$ representerer en svart go-stein).

• Hvis den $8$. go-steinen er hvit ($\circ$), har den samme farge som steinen lengst til høyre, så vi legger den slik den er. Dermed blir go-steinene på bordet:

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

• Hvis den $8$. go-steinen er svart ($\bullet$), har den ulik farge fra steinen lengst til høyre ($\circ$), så vi fjerner først de $3$ sammenhengende hvite go-steinene ($\circ$) ved høyre ende av bordet og erstatter dem med svarte go-steiner ($\bullet$). Deretter legger vi den $8$. go-steinen lengst til høyre. Dermed blir go-steinene på bordet:

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

Gitt rekkefølgen på go-steinene som skal legges som inndata, skriv et program som finner antallet hvite go-steiner som ligger på bordet etter at alle $n$ go-steinene er lagt.

Inndata

På den $1$. linjen står et positivt heltall $n$ ($1 \le n \le 100\,000$). Fra og med den $2$. linjen står det på linje $i+1$ ($1 \le i \le n$) et heltall $c_{i}$ som angir fargen på den $i$-te go-steinen som legges, der $c_{i}$ lik $0$ betyr at den $i$-te go-steinen er hvit, og $1$ betyr at den $i$-te go-steinen er svart.

Av testdataene oppfyller $50\%$ av poengene $n \le 10\,000$.

Utdata

Skriv ut $1$ linje som kun inneholder antallet hvite go-steiner på bordet etter at alle $n$ go-steinene er lagt.

Eksempler på inndata og utdata

Eksempelinndata 1

8
1
0
1
1
0
0
0
0

Eksempelutdata 1

6

Eksempelinndata 2

8
1
0
1
1
0
0
0
1

Eksempelutdata 2

2