題目描述

我們在桌子上擺放白色與黑色的圍棋子來玩遊戲。首先在桌子的左端放一顆圍棋子，接著在從左往右第 $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