题目描述

小明来到了莆田旅游，想要好好感受一下莆田的风土人情和美景美食。小明在各个景点观赏了很多花卉，在众多的品种中，小明最喜欢莆田市的市花——月季。

小明经常购买月季带回自己的花园里种植，而且只会购买玫红色花瓣的月季，但是玫红色花瓣的月季还分 A 品种和 B 品种，俩品种外观上差异很小，肉眼难以区分，但是如果种植在同一个花盆里会互相影响生长。由于小明分辨不出 A 品种和 B 品种的区别，因此会不定期请花卉专家来鉴定所有未知品种的月季（在请花卉专家之前新购买的月季都是未知品种的），确认每一株月季的品种。

花园里的每个花盆最多能种植两株月季，为了让月季都能健康生长，小明需要保证任一时刻种植在同一花盆里的月季是同一品种。但同时应该尽可能减少使用的花盆数量。

现在假设一开始花园里没有月季，已知小明接下来 $n$ 天里，每天会进行一项活动：要么买新的一株月季，要么请花卉专家。请你计算最少需要提前准备好多少个空花盆才能保证这 $n$ 天里每一天所有的月季都能健康生长？

注意：月季买回来当天必须种到花盆中；种到花盆中的月季随时可以移栽到其他花盆中；小明购买的月季除了 A 和 B 品种外不会出现其他品种。

输入格式

第一行一个整数 $n$ 表示天数

接下来 $n$ 行，每行一个正整数 $a_i$，对应每天的活动类型，活动类型只有两种情况（$1$ 和 $2$）：

1 : 购买新的一株月季 2 : 请花卉专家

输出格式

一个整数，表示小明最少需要提前准备好的空花盆数量。

测试样例

输入样例 #1

3
1
1
1

输出样例 #1

3

输入样例 #2

5
1
1
1
2
1

输出样例 #2

3

样例说明

第一组样例，小明买了三株未知品种的月季，为了保证健康生长，只能使用 $3$ 个花盆分开种植。

第二组样例，小明先买了三株未知品种的月季，此时需要 $3$ 个花盆；接着请了花卉专家鉴定品种，此时三株月季要么三株都是同一品种，要么两株同品种另一株不同品种，这两种情况都需要 $2$ 个花盆，小明可以通过移栽月季，让使用的花盆数量减少到 $2$ 个；最后一天又买了一株未知品种的月季，为了保证健康生长，此时共需 $3$ 个花盆。

数据范围

对于 $10\%$ 的数据，小明每天的活动都相同。

另有 $20\%$ 的数据，小明只会请一次花卉专家。

对于 $100\%$ 的数据，$1 \le n \le 10^5, 1 \le a_i \le 2$。