Problema

Giochiamo disponendo pietre da go bianche e nere su un tavolo. Per prima cosa mettiamo una pietra da go all'estremità sinistra del tavolo. Poi mettiamo una pietra da go nella $2$-a posizione da sinistra. Ripetendo questa operazione $n$ volte, allineiamo $n$ pietre da go in un'unica fila orizzontale. Tuttavia, quando si posiziona una nuova $i$-esima pietra da go, si sostituiscono le pietre sul tavolo secondo le seguenti regole:

• Se $i$ è dispari: senza sostituire le pietre già presenti sul tavolo, si posiziona la nuova pietra nella $i$-esima posizione da sinistra.
• Se $i$ è pari: se il colore della nuova pietra posizionata nella $i$-esima posizione da sinistra è uguale al colore della pietra più a destra sul tavolo, si posiziona la nuova pietra nella $i$-esima posizione da sinistra senza sostituire le pietre sul tavolo. Altrimenti, cioè se il colore della nuova pietra nella $i$-esima posizione da sinistra è diverso dal colore della pietra più a destra sul tavolo, prima si rimuovono tutte le pietre consecutive dello stesso colore all'estremità destra del tavolo e si sostituiscono con pietre dello stesso colore della $i$-esima pietra. Poi si posiziona la $i$-esima pietra all'estremità destra del tavolo.

Ad esempio, supponiamo che dopo aver posizionato le prime $7$ pietre da go la situazione sia:

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

(dove $\circ$ rappresenta una pietra bianca e $\bullet$ rappresenta una pietra nera).

• Se l'$8$-a pietra è bianca ($\circ$), poiché ha lo stesso colore della pietra più a destra, viene posizionata così com'è. Pertanto, le pietre sul tavolo diventano:

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

• Se l'$8$-a pietra è nera ($\bullet$), poiché il suo colore è diverso da quello della pietra più a destra ($\circ$), prima si rimuovono le $3$ pietre bianche consecutive ($\circ$) all'estremità destra del tavolo e si sostituiscono con pietre nere ($\bullet$). Poi si posiziona l'$8$-a pietra all'estremità destra. Pertanto, le pietre sul tavolo diventano:

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

Dato in input l'ordine delle pietre da go da posizionare, scrivi un programma per trovare il numero di pietre bianche presenti sul tavolo dopo aver finito di allineare le $n$ pietre.

Input

Sulla $1$-a riga è scritto un intero positivo $n$ ($1 \le n \le 100\,000$). Dalla $2$-a riga in poi, sulla $i+1$-esima riga ($1 \le i \le n$), è scritto un intero $c_{i}$ che rappresenta il colore della $i$-esima pietra da posizionare: se $c_{i}$ vale $0$ significa che la $i$-esima pietra è bianca, mentre se vale $1$ significa che la $i$-esima pietra è nera.

Nei dati di valutazione, per il $50\%$ del punteggio vale $n \le 10\,000$.

Output

Stampa $1$ riga contenente solo il numero di pietre da go bianche presenti sul tavolo dopo aver finito di posizionare le $n$ pietre.

Esempi di input e output

Esempio di input 1

8
1
0
1
1
0
0
0
0

Esempio di output 1

6

Esempio di input 2

8
1
0
1
1
0
0
0
1

Esempio di output 2

2