Public Judge

pjudge

Time Limit: 1 s Memory Limit: 1024 MB Total points: 100 Hackable ✓

# 21701. 【NOIP Round #4】咖啡

Statistics

在花花大学,学生需要按照顺序去 $n$ 间教室上课。第 $i$ 间教室有一个属性 $s_i \in \{0, 1\}$。若 $s_i = 1$,表示这间教室有一座咖啡机;若 $s_i = 0$,表示这间教室没有咖啡机。

你是花花大学的一名学生。在一间有咖啡机的教室里,你可以通过饮用一杯咖啡来使得自己不会犯困。特别地,在你离开一间有咖啡机的教室后,你可以携带最多两杯咖啡(每只手可以拿一杯)前往下一间教室,这样即使那间教室没有咖啡机,你可以通过饮用你携带的咖啡来提神。

现在你想要知道,你最多可以在多少间教室内饮用咖啡。

输入格式

输入的第一行包含一个整数 $n$。

接下来一行,包含一个长度为 $n$ 的,只由字符 0 与字符 1 构成的字符串 $s$,其中第 $i$ 个字符 $s_i$ 描述了第 $i$ 间教室是否有咖啡机。

输出格式

输出一行一个整数,表示答案。

样例数据

样例 1 输入

6
010100

样例 1 输出

5

样例 2 输入

10
0000000110

样例 2 输出

3

样例 3

见下发文件。

子任务

对于 $100\%$ 的数据,$1 \le n \le 10^5$。

测试点编号 $n\le $
$1$ $1$
$2 \sim 6$ $10$
$7 \sim 8$ $5\,000$
$9 \sim 20$ $10^5$