Uppgift

Vi spelar ett spel genom att lägga ut vita och svarta go-stenar på ett bord. Först lägger vi en go-sten vid bordets vänstra ände. Därefter lägger vi en go-sten på den $2$:a platsen från vänster. Genom att upprepa detta $n$ gånger radar vi upp $n$ go-stenar i en enda horisontell rad. När vi lägger ut en ny $i$:te go-sten byter vi dock ut go-stenarna på bordet enligt följande regler:

• När $i$ är udda: Utan att byta ut de go-stenar som redan ligger på bordet lägger vi den nya go-stenen på den $i$:te platsen från vänster.
• När $i$ är jämnt: Om färgen på den nya go-stenen som läggs på den $i$:te platsen från vänster är densamma som färgen på go-stenen längst till höger på bordet, lägger vi den nya go-stenen på den $i$:te platsen från vänster utan att byta ut go-stenarna på bordet. I annat fall, det vill säga om färgen på den nya go-stenen på den $i$:te platsen från vänster skiljer sig från färgen på go-stenen längst till höger på bordet, tar vi först bort alla sammanhängande go-stenar av samma färg vid bordets högra ände och ersätter dem med go-stenar av samma färg som den $i$:te go-stenen. Därefter lägger vi den $i$:te go-stenen vid bordets högra ände.

Anta till exempel att ställningen efter att de första $7$ go-stenarna har lagts ut är:

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

(där $\circ$ betecknar en vit go-sten och $\bullet$ betecknar en svart go-sten).

• Om den $8$:e go-stenen är vit ($\circ$) har den samma färg som stenen längst till höger, så vi lägger dit den som den är. Därmed blir go-stenarna på bordet:

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

• Om den $8$:e go-stenen är svart ($\bullet$) skiljer sig dess färg från stenen längst till höger ($\circ$), så vi tar först bort de $3$ sammanhängande vita go-stenarna ($\circ$) vid bordets högra ände och ersätter dem med svarta go-stenar ($\bullet$). Sedan lägger vi den $8$:e go-stenen längst till höger. Därmed blir go-stenarna på bordet:

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

Givet ordningen på de go-stenar som ska läggas ut som indata, skriv ett program som beräknar antalet vita go-stenar som ligger på bordet efter att alla $n$ go-stenar har lagts ut.

Indata

På den $1$:a raden står ett positivt heltal $n$ ($1 \le n \le 100\,000$). Från och med den $2$:a raden står på rad $i+1$ ($1 \le i \le n$) ett heltal $c_{i}$ som anger färgen på den $i$:te go-stenen som läggs ut, där $c_{i}$ lika med $0$ anger att den $i$:te go-stenen är vit och $1$ anger att den $i$:te go-stenen är svart.

Av testdata uppfyller $50\%$ av poängen villkoret $n \le 10\,000$.

Utdata

Skriv ut $1$ rad som enbart innehåller antalet vita go-stenar på bordet efter att alla $n$ go-stenar har lagts ut.

Exempel på indata och utdata

Exempelindata 1

8
1
0
1
1
0
0
0
0

Exempelutdata 1

6

Exempelindata 2

8
1
0
1
1
0
0
0
1

Exempelutdata 2

2