题目描述

Ducati拥有一个$01$字符串，即这个字符串里只包含$0$或$1$。
现在，Ducati想从这个字符串里拿出一些数字（$0$或$1$），并使得这些数字的和最大。但是相邻的两个数字不能同时被拿去。
现在Ducati会询问你它们的最大可能和。

输入格式

第一行输入一个整数$n$，表示这个$01$串的长度为$n$。
第二行输入这个$01$串。

输出格式

一行输出最大的和。

输入输出样例1

输入

5
11001

输出

2

输入输出样例2

输入

6
111111

输出

3

样例解释

在样例1中，取位置$1$,$5$或$2$,$5$都能得到答案$2$，但是位置$1$和$2$不能同时取。
在样例2中，取位置$1,3,5$可以得到答案$3$，注意取的方式不唯一。

数据范围

对于100%的数据满足，$1≤n,mod≤2×10^9$且$mod$为质数。
Subtask 1(20pts):$n≤10$。
Subtask 2(30pts):$n≤10^5$。
Subtask 3(50pts):无特殊限制。

贡献者

题面:Ducati
数据，核题:b6e0