Problème

On joue en alignant des pierres de go blanches et noires sur une table. On place d'abord une pierre de go à l'extrémité gauche de la table. Ensuite, on place une pierre de go à la $2$-ème position en partant de la gauche. On répète cela $n$ fois pour aligner $n$ pierres de go sur une seule rangée horizontale. Toutefois, lorsqu'on place une nouvelle $i$-ème pierre de go, on remplace les pierres sur la table selon les règles suivantes :

• Si $i$ est impair : sans remplacer les pierres déjà présentes sur la table, on place la nouvelle pierre à la $i$-ème position en partant de la gauche.
• Si $i$ est pair : si la couleur de la nouvelle pierre placée à la $i$-ème position en partant de la gauche est identique à celle de la pierre située à l'extrémité droite de la table, on place la nouvelle pierre à la $i$-ème position en partant de la gauche sans remplacer les pierres sur la table. Sinon, c'est-à-dire si la couleur de la nouvelle pierre placée à la $i$-ème position en partant de la gauche diffère de celle de la pierre située à l'extrémité droite de la table, on retire d'abord toutes les pierres consécutives de même couleur situées à l'extrémité droite de la table et on les remplace par des pierres de la même couleur que la $i$-ème pierre. Puis on place la $i$-ème pierre à l'extrémité droite de la table.

Par exemple, supposons qu'après avoir placé les $7$ premières pierres de go, l'état soit :

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

(où $\circ$ représente une pierre blanche et $\bullet$ représente une pierre noire).

• Si la $8$-ème pierre est blanche ($\circ$), comme elle est de la même couleur que la pierre à l'extrémité droite, on la pose telle quelle. Les pierres sur la table deviennent donc :

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

• Si la $8$-ème pierre est noire ($\bullet$), comme sa couleur diffère de celle de la pierre à l'extrémité droite ($\circ$), on retire d'abord les $3$ pierres blanches consécutives ($\circ$) situées à l'extrémité droite de la table et on les remplace par des pierres noires ($\bullet$). Puis on place la $8$-ème pierre à l'extrémité droite. Les pierres sur la table deviennent donc :

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

Étant donné en entrée l'ordre des pierres de go à placer, écrivez un programme pour déterminer le nombre de pierres blanches présentes sur la table une fois les $n$ pierres alignées.

Entrée

Sur la $1$-ère ligne est écrit un entier strictement positif $n$ ($1 \le n \le 100\,000$). À partir de la $2$-ème ligne, sur la $i+1$-ème ligne ($1 \le i \le n$), est écrit un entier $c_{i}$ représentant la couleur de la $i$-ème pierre à placer : si $c_{i}$ vaut $0$, cela indique que la $i$-ème pierre est blanche, et s'il vaut $1$, que la $i$-ème pierre est noire.

Parmi les données d'évaluation, $50\%$ des points satisfont $n \le 10\,000$.

Sortie

Affichez $1$ ligne contenant uniquement le nombre de pierres de go blanches présentes sur la table après avoir aligné les $n$ pierres.

Exemples d'entrée et de sortie

Exemple d'entrée 1

8
1
0
1
1
0
0
0
0

Exemple de sortie 1

6

Exemple d'entrée 2

8
1
0
1
1
0
0
0
1

Exemple de sortie 2

2