题目描述

我们在桌子上摆放白色与黑色的围棋子来玩游戏。首先在桌子的左端放一颗围棋子，接着在从左往右第 $2$ 个位置放一颗围棋子。重复这一过程 $n$ 次，将 $n$ 颗围棋子排成横着的一排。但是，当新放上第 $i$ 颗围棋子时，需要按照以下规则替换桌子上的围棋子：

• 当 $i$ 为奇数时：不替换桌子上原有的围棋子，直接将新的围棋子放在从左往右第 $i$ 个位置。
• 当 $i$ 为偶数时：如果新放在从左往右第 $i$ 个位置的围棋子的颜色与桌子上最右端的围棋子的颜色相同，则不替换桌子上的围棋子，直接将新的围棋子放在从左往右第 $i$ 个位置。否则，即当新放在从左往右第 $i$ 个位置的围棋子的颜色与桌子上最右端的围棋子的颜色不同时，首先将桌子上最右端连续的同色围棋子全部取走，替换为与第 $i$ 颗围棋子同色的围棋子，然后在桌子的最右端放上第 $i$ 颗围棋子。

例如，假设在放好最初的 $7$ 颗围棋子时，状态如下：

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

（其中 $\circ$ 表示白棋子，$\bullet$ 表示黑棋子。）

• 当第 $8$ 颗围棋子为白色（$\circ$）时，由于它与最右端的围棋子同色，直接放上即可。因此，桌子上的围棋子变为：

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

• 当第 $8$ 颗围棋子为黑色（$\bullet$）时，由于它的颜色与最右端的围棋子（$\circ$）不同，首先将桌子最右端连续的 $3$ 颗白棋子（$\circ$）取走，替换为黑棋子（$\bullet$），然后在最右端放上第 $8$ 颗围棋子。因此，桌子上的围棋子变为：

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

当给定所放围棋子的顺序作为输入时，请编写程序求出在摆完 $n$ 颗围棋子之后，桌子上白色围棋子的个数。

输入格式

第 $1$ 行写有一个正整数 $n$ ($1 \le n \le 100\,000$)。从第 $2$ 行起的第 $i+1$ 行 ($1 \le i \le n$) 写有表示第 $i$ 个放置的围棋子颜色的整数 $c_{i}$，其中 $c_{i}$ 为 $0$ 表示第 $i$ 个放置的围棋子颜色为白，为 $1$ 表示第 $i$ 个放置的围棋子颜色为黑。

在评测数据中，占总分 $50\%$ 的数据满足 $n \le 10\,000$。

输出格式

输出仅包含 $1$ 行，为摆完 $n$ 颗围棋子之后桌子上白色围棋子的个数。

样例输入与输出

样例输入 1

8
1
0
1
1
0
0
0
0

样例输出 1

6

样例输入 2

8
1
0
1
1
0
0
0
1

样例输出 2

2