Problema

Jugamos colocando piedras de go blancas y negras sobre una mesa. Primero colocamos una piedra de go en el extremo izquierdo de la mesa. A continuación colocamos una piedra de go en la $2$-ª posición desde la izquierda. Repitiendo esto $n$ veces, alineamos $n$ piedras de go en una sola fila horizontal. Sin embargo, al colocar una nueva $i$-ésima piedra de go, reemplazamos las piedras sobre la mesa siguiendo estas reglas:

• Cuando $i$ es impar: sin reemplazar las piedras que ya estaban en la mesa, colocamos la nueva piedra en la $i$-ésima posición desde la izquierda.
• Cuando $i$ es par: si el color de la nueva piedra que se coloca en la $i$-ésima posición desde la izquierda es igual al color de la piedra situada en el extremo derecho de la mesa, colocamos la nueva piedra en la $i$-ésima posición desde la izquierda sin reemplazar las piedras de la mesa. En caso contrario, es decir, si el color de la nueva piedra en la $i$-ésima posición desde la izquierda es diferente del color de la piedra en el extremo derecho de la mesa, primero retiramos todas las piedras consecutivas del mismo color situadas en el extremo derecho de la mesa y las reemplazamos por piedras del mismo color que la $i$-ésima piedra. Luego colocamos la $i$-ésima piedra en el extremo derecho de la mesa.

Por ejemplo, supongamos que tras colocar las primeras $7$ piedras de go, el estado es:

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

(donde $\circ$ representa una piedra blanca y $\bullet$ representa una piedra negra).

• Si la $8$-ª piedra es blanca ($\circ$), como tiene el mismo color que la piedra del extremo derecho, la colocamos tal cual. Por lo tanto, las piedras sobre la mesa quedan así:

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

• Si la $8$-ª piedra es negra ($\bullet$), como su color difiere del de la piedra del extremo derecho ($\circ$), primero retiramos las $3$ piedras blancas consecutivas ($\circ$) del extremo derecho de la mesa y las reemplazamos por piedras negras ($\bullet$). Después colocamos la $8$-ª piedra en el extremo derecho. Por lo tanto, las piedras sobre la mesa quedan así:

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

Dado como entrada el orden de las piedras de go a colocar, escribe un programa que calcule el número de piedras blancas que quedan sobre la mesa después de haber terminado de colocar las $n$ piedras.

Entrada

En la $1$-ª línea está escrito un entero positivo $n$ ($1 \le n \le 100\,000$). A partir de la $2$-ª línea, en la línea $i+1$ ($1 \le i \le n$), está escrito un entero $c_{i}$ que representa el color de la $i$-ésima piedra a colocar: si $c_{i}$ es $0$, indica que la $i$-ésima piedra es blanca, y si es $1$, indica que la $i$-ésima piedra es negra.

De los datos de evaluación, el $50\%$ de la puntuación cumple $n \le 10\,000$.

Salida

Imprime $1$ sola línea que contenga únicamente el número de piedras de go blancas sobre la mesa tras terminar de colocar las $n$ piedras.

Ejemplos de entrada y salida

Ejemplo de entrada 1

8
1
0
1
1
0
0
0
0

Ejemplo de salida 1

6

Ejemplo de entrada 2

8
1
0
1
1
0
0
0
1

Ejemplo de salida 2

2