I. 圈养豚鼠

• 时间限制：1 秒/组测试点
• 内存限制：256 MB/组测试点
• 输入输出：标准流
• 编程语言：无限制

题目摘要

* 我们姑且认为，豚鼠只有两种性别 —— 雄性和雌性 *

Dasha 每天的计划：要么买一只豚鼠，要么医生检查她全部已有豚鼠的性别。
不过豚鼠需要笼子，而店家只提供“鸳鸯笼子”（每笼至多居住 $2$ 只豚鼠）。
但 Dasha 决不允许“异性”豚鼠同居。

请帮 Dasha 计算：最坏情况下，需要多少笼子，以确保没有异性同居。

输入描述

对于每组数据，
第一行为一个整数 $n\ (1\le n\le 10^5)$—— Dasha 计划的天数。
第二行包含 $n$ 个整数 $b_1,\ b_2,\ b_3,\ \dots,\ b_n\ (1\le b_i\le 2)$—— Dasha 的计划。
如果 $b_i=1$，则在第 $i$ 天，Dasha 将买一只新的豚鼠。
如果 $b_i=2$，则在第 $i$ 天，医生会过来帮助 Dasha 确定当前所有豚鼠的性别。

承诺所有输入数据集的 $n$ 的总和不会超过 $10^5$。

输出描述

对于每组输入数据，输出一个整数 $x$ —— 无论豚鼠们的性别如何，
Dasha 在没有异性豚鼠同笼的情况下，安置他们最少需要购买笼子的数量。

输入输出样例

样例 1

样例输入

3
1 1 1

样例输出

3

样例 2

样例输入

3
2 2 2

样例输出

0

样例 3

样例输入

5
1 1 1 2 1

样例输出

3

样例 4

样例输入

10
1 2 1 2 1 2 1 2 1 2

样例输出

4

样例 5

样例输入

20
1 2 1 1 1 1 1 2 1 2 1 2 2 1 1 1 1 1 1 1

样例输出

12

样例 6

样例输入

20
2 1 1 2 1 1 2 1 2 2 1 1 1 2 2 1 1 1 1 2

样例输出

9