Problem

We play a game by placing white and black Go stones on a table. First, we place a Go stone at the left end of the table. Next, we place a Go stone at the $2$-nd position from the left. Repeating this $n$ times, we line up $n$ Go stones in a single horizontal row. However, when placing a new $i$-th Go stone, we replace the Go stones on the table according to the following rules:

• When $i$ is odd: Without replacing the Go stones already on the table, place the new Go stone at the $i$-th position from the left.
• When $i$ is even: If the color of the new Go stone placed at the $i$-th position from the left is the same as the color of the rightmost Go stone on the table, place the new Go stone at the $i$-th position from the left without replacing the Go stones on the table. Otherwise, that is, if the color of the new Go stone placed at the $i$-th position from the left differs from the color of the rightmost Go stone on the table, first remove all consecutive Go stones of the same color at the right end of the table and replace them with Go stones of the same color as the $i$-th Go stone. Then place the $i$-th Go stone at the right end of the table.

For example, suppose that after placing the first $7$ Go stones, the state is:

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

(where $\circ$ represents a white Go stone and $\bullet$ represents a black Go stone).

• If the $8$-th Go stone is white ($\circ$), since it has the same color as the rightmost Go stone, we place it as is. Therefore, the Go stones on the table become:

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

• If the $8$-th Go stone is black ($\bullet$), since its color differs from the rightmost Go stone ($\circ$), we first remove the $3$ consecutive white Go stones ($\circ$) at the right end of the table and replace them with black Go stones ($\bullet$). Then we place the $8$-th Go stone at the right end. Therefore, the Go stones on the table become:

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

Given the order of Go stones to be placed as input, write a program to find the number of white Go stones on the table after all $n$ Go stones have been placed.

Input

On the $1$-st line, a positive integer $n$ ($1 \le n \le 100\,000$) is written. On the $i+1$-th line ($1 \le i \le n$) from the $2$-nd line onwards, an integer $c_{i}$ representing the color of the $i$-th Go stone to be placed is written, where $c_{i}$ being $0$ indicates that the color of the $i$-th Go stone is white, and $1$ indicates that the color of the $i$-th Go stone is black.

Of the test data, for $50\%$ of the score, $n \le 10\,000$ holds.

Output

Print $1$ line containing only the number of white Go stones on the table after all $n$ Go stones have been placed.

Sample Input and Output

Sample Input 1

8
1
0
1
1
0
0
0
0

Sample Output 1

6

Sample Input 2

8
1
0
1
1
0
0
0
1

Sample Output 2

2