测试数据来自 b6e0_OJ/1008

题目描述

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\le n\le10^6\)
Subtask 1(20%): \(n\le10\)。
Subtask 2(30%): \(n\le1000\)。
Subtask 3(50%): 无特殊限制。

贡献者

题面，数据: b6e0
核题: Ducati