Aufgabe

Wir spielen ein Spiel, indem wir weiße und schwarze Go-Steine auf einem Tisch in einer Reihe anordnen. Zuerst legen wir einen Go-Stein an das linke Ende des Tisches. Als Nächstes legen wir einen Go-Stein an die $2$. Position von links. Indem wir dies $n$-mal wiederholen, reihen wir $n$ Go-Steine in einer einzigen horizontalen Reihe auf. Wenn wir jedoch den neuen $i$-ten Go-Stein hinlegen, ersetzen wir die Go-Steine auf dem Tisch nach den folgenden Regeln:

• Wenn $i$ ungerade ist: Die bereits auf dem Tisch liegenden Go-Steine werden nicht ersetzt, und der neue Go-Stein wird an die $i$-te Position von links gelegt.
• Wenn $i$ gerade ist: Wenn die Farbe des neuen Go-Steins, der an die $i$-te Position von links gelegt wird, mit der Farbe des am weitesten rechts liegenden Go-Steins auf dem Tisch übereinstimmt, werden die Go-Steine auf dem Tisch nicht ersetzt und der neue Go-Stein wird an die $i$-te Position von links gelegt. Andernfalls, also wenn sich die Farbe des neuen Go-Steins an der $i$-ten Position von links von der Farbe des am weitesten rechts liegenden Go-Steins auf dem Tisch unterscheidet, werden zuerst alle aufeinanderfolgenden Go-Steine gleicher Farbe am rechten Ende des Tisches entfernt und durch Go-Steine derselben Farbe wie der $i$-te Go-Stein ersetzt. Anschließend wird der $i$-te Go-Stein an das rechte Ende des Tisches gelegt.

Angenommen, nachdem die ersten $7$ Go-Steine gelegt wurden, liegt folgender Zustand vor:

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

(wobei $\circ$ für einen weißen Go-Stein und $\bullet$ für einen schwarzen Go-Stein steht).

• Wenn der $8$. Go-Stein weiß ($\circ$) ist, hat er dieselbe Farbe wie der Stein ganz rechts und wird einfach dazugelegt. Somit sehen die Go-Steine auf dem Tisch wie folgt aus:

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

• Wenn der $8$. Go-Stein schwarz ($\bullet$) ist, unterscheidet sich seine Farbe vom Stein ganz rechts ($\circ$); daher werden zuerst die $3$ aufeinanderfolgenden weißen Go-Steine ($\circ$) am rechten Ende des Tisches entfernt und durch schwarze Go-Steine ($\bullet$) ersetzt. Dann wird der $8$. Go-Stein an das rechte Ende gelegt. Somit sehen die Go-Steine auf dem Tisch wie folgt aus:

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

Schreibe ein Programm, das bei gegebener Reihenfolge der zu legenden Go-Steine die Anzahl der weißen Go-Steine bestimmt, die auf dem Tisch liegen, nachdem alle $n$ Go-Steine gelegt wurden.

Eingabe

In der $1$. Zeile steht eine positive ganze Zahl $n$ ($1 \le n \le 100\,000$). Ab der $2$. Zeile steht in der $i+1$-ten Zeile ($1 \le i \le n$) eine ganze Zahl $c_{i}$, welche die Farbe des $i$-ten zu legenden Go-Steins angibt: Ist $c_{i}$ gleich $0$, bedeutet dies, dass der $i$-te Go-Stein weiß ist; ist sie $1$, bedeutet dies, dass der $i$-te Go-Stein schwarz ist.

Von den Testdaten erfüllen $50\%$ der Punkte die Bedingung $n \le 10\,000$.

Ausgabe

Gib $1$ Zeile aus, die ausschließlich die Anzahl der weißen Go-Steine auf dem Tisch enthält, nachdem alle $n$ Go-Steine gelegt wurden.

Ein- und Ausgabebeispiele

Eingabebeispiel 1

8
1
0
1
1
0
0
0
0

Ausgabebeispiel 1

6

Eingabebeispiel 2

8
1
0
1
1
0
0
0
1

Ausgabebeispiel 2

2