T568935 「2025 YAC Round 4」不要为难鸟脑袋了！

「2025 YAC Round 4」B 题

夜雀食堂今天又举办料理大赛了，[米斯蒂娅](https://mzh.moegirl.org.cn/%E7%B1%B3%E6%96%AF%E8%92%82%E5%A8%85%C2%B7%E8%90%9D%E8%95%BE%E6%8B%89) 是头号种子选手！具体规则如下： 夜雀食堂的厨房有一排 $n$ 个灶台，初始情况下所有的灶台都是空余的。 本次料理大赛采用回合制，并且每一回合可以制作的一道菜品已经指定好了。米斯蒂娅每个回合可以开始制作一道新的菜品，也可以跳过这道菜不制作。 开始制作一道菜需要占用一定数量的灶台。有的菜只需要占用 $1$ 个灶台，有的菜则需要占用 **相邻** 的 $2$ 个灶台。如果没有空余足够的灶台制作一道新的菜品，可以撤除一些之前已经开始制作的菜品。 **每个开始制作后的菜品从开始制作的回合起，每个回合会产生 $1$ 个单位的美味值。** 如果一道菜后续在某个回合被撤除了，从这个回合开始也不再会产生美味值。 求米斯蒂娅可能得到的 **美味值总和的最大值** 是多少。

第一行输入一个整数 $n$（$1 \le n \le 10^5$），表示灶台个数。 第二行输入一个字符串 $s$（$s_i \in \{ ‘1’, ‘2’ \}$，$i$ 从 $0$ 开始），表示每一回合指定可以制作的一道菜品。 如果第 $i$ 个字符为 $‘1’$ ，表示第 $i$ 回合的菜需要占用 $1$ 个灶台；否则，表示第 $i$ 回合的菜需要占用 **相邻** 的 $2$ 个灶台。字符串 $s$ 的长度不超过 $10^5$。

输出一个整数表示答案。

#### 样例解释 共有 $3$ 个灶台。 第一回合，开始制作第 $1$ 道菜，占用第 $1$ 个灶台。产生 $1$ 个单位美味值。 第二回合，开始制作第 $2$ 道菜，占用相邻的第 $2,3$ 个灶台。产生 $1 + 1 = 2$ 个单位美味值。 第三回合，撤除第 $2$ 道菜，第 $2,3$ 个灶台空余出来。开始制作第 $3$ 道菜，占用第 $2$ 个灶台。产生 $1 + 1 = 2$ 个单位美味值。 第四回合，不制作新菜品。产生 $1 + 1 = 2$ 个单位美味值。 第五个回合，开始制作第 $5$ 道菜，占用第 $3$ 个灶台。产生 $1 + 1 + 1 = 3$ 个单位美味值。 因此，共产生 $10$ 个单位美味值。没有其他方案使得总得分更大。