Audrey 是米哈游的系统管理员！她的工作是管理机房，并保证她最喜欢的游戏《崩坏：星穹铁道》（Honkai: Star Rail）正常运行。

米哈游的机房被划分为一排单走廊的区域，其中一些区域安装了服务器。部分服务器已经处于开启状态。

Audrey 急需开启更多的服务器。然而，机房的通风条件很差，如果相邻区域的两个服务器同时开启，机房就会过热。

Audrey 不能关闭已经开启的服务器。请计算在不导致机房过热的前提下，Audrey 最多可以从当前关闭的服务器中再开启多少台服务器。

输入格式

输入的第一行包含一个整数 $n$ ($1 \le n \le 3 \cdot 10^5$)。

输入的第二行包含一个长度为 $n$ 的三进制字符串 $s$，表示机房的状况。字符 0 表示该区域没有服务器，字符 1 表示该区域有一台关闭的服务器，字符 2 表示该区域有一台开启的服务器。

保证机房当前没有过热。

输出格式

输出一个整数，表示 Audrey 在当前关闭的服务器中最多可以额外开启的服务器数量。

样例

输入样例 1

7
1112111

输出样例 1

2

输入样例 2

3
212

输出样例 2

0

输入样例 3

3
101

输出样例 3

2