题目描述

有 $n$ 个房间排成一排，每个房间前有一个守卫。守卫类型有三种：

1. 类型 0：恢复已经消耗的所有普通护盾和特殊护盾。
2. 类型 1：需要消耗一张普通护盾才能通过。
3. 类型 2：需要消耗一张特殊护盾才能通过。

初始时普通护盾数量无限，特殊护盾需要在进入第一个房间前购买。每次通过类型 2 的守卫会消耗一张特殊护盾，遇到类型 0 的守卫后，之前消耗的特殊护盾会全部恢复。

求最少需要购买多少张特殊护盾，才能依次通过所有守卫。

输入格式

第一行一个整数 $n$，表示守卫数量。

第二行 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个守卫的类型，取值为 0、1 或 2。

输出格式

输出一行一个整数，表示最少需要购买的特殊护盾数量。

6
1 2 0 1 2 2

2

5
2 2 1 2 1

3

4
1 0 1 0

0

样例解释

样例 1 中，通过第 $2$ 个守卫会消耗一张特殊护盾；第 $3$ 个守卫会恢复护盾。之后第 $5,6$ 个守卫连续需要两张特殊护盾，因此答案为 $2$。

样例 2 中没有类型 0 的守卫，特殊护盾不会恢复，一共需要通过 $3$ 个类型 2 的守卫，因此答案为 $3$。

样例 3 中没有类型 2 的守卫，不需要购买特殊护盾。

数据范围与约定

特殊性质 A：没有类型 0 的守卫。

特殊性质 B：没有类型 1 的守卫。

对于所有数据，$1 \le n \le 10000$。

下发样例

下发样例下载