Description

小 Vasya 正在玩一个新的电脑游戏——回合制策略游戏 Energy Tycoon。

游戏的规则很简单：

棋盘上有 $n$ 个槽位排成一行。

有发电厂，一个发电厂占据一个或两个连续的槽位，并产生一个单位的能量。

每回合游戏允许你建造一个新的发电厂，如果你愿意可以将其放在棋盘上。如果没有地方放新的发电厂，你可以移除一些旧的发电厂。

每回合结束后，计算机会计算棋盘上发电厂产生的能量总量并将其加到总分中。

Vasya 已经知道他每回合可以建造的发电厂类型。现在他想知道，他能获得的最大可能分数是多少。你能帮助他吗？

Input Format

输入的第一行包含一个整数 $n (1 \le n \le 100 000)$ —— 棋盘上的槽位数。第二行包含字符串 $s$。字符串的第 $i$ 个字符是 $1$ 表示你可以在第 $i$ 回合建造一个占一个槽位的发电厂，字符是 $2$ 表示你可以在第 $i$ 回合建造一个占两个槽位的发电厂。回合数不超过 $100 000$。

Output Format

输出应包含一个整数 —— 可以达到的最大分数。

3
21121

10

2
12

2

2
211

4

Hint

时间限制：2 秒，内存限制：256 MB。

题面翻译由 ChatGPT-4o 提供。