題目描述

我哋喺張枱度擺放白色同黑色嘅圍棋子嚟玩遊戲。首先喺張枱嘅左端放一粒圍棋子，跟住喺由左邊數起第 $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