题目描述

面条老师 现在在玩一个游戏。游戏中共有$n$个房间，每个房间前有一个守卫。

每个守卫具有以下属性之一：

• 内鬼守卫，可以帮助你将之前消耗过的全部普通护盾和特殊护盾修复。
• 普通守卫，需要消耗一张普通护盾才能通过。
• 特殊守卫，需要消耗一张特殊护盾才能通过。

初始时 面条老师 具有无限个普通护盾，另外 面条老师 可以在游戏开始前花费金币购买特殊护盾。

面条老师 想要知道最少购买几个特殊护盾才能保证他完成游戏。

输入格式

第一行一个正整数$n$，表示一共有$n$个守卫。

接下来一行$n$个整数，依次代表每个守卫。0表示内鬼守卫；1表示普通守卫，2表示特殊守卫。

输出格式

一行一个整数表示最少购买几个特殊护盾才能完成游戏。

6
1 2 0 1 2 2 

2

样例解释 1

面条老师 需要提前准备两个特殊护盾。通过第二个守卫后在第三个守卫处恢复完护盾，之后手上持有两个特殊护盾，分别用于通过第五和第六两个守卫。

数据规模与约定

每组数据点10分，共10组数据。

对于所有数据，均有$1 \le n \le 10,000$

大样例

大样例下载