题目描述

Little Vasya is playing a new computer game -- turn-based strategy Energy Tycoon.

The rules of the game are quite simple:

The board contains $n$ slots arranged in a line.

There are power plants, one power plant occupies one or two consecutive slots, and produces one unit of energy.

Each turn the game allows you to build one new power plant, you can put it on the board if you wish. If there is no place for the new power plant, you can remove some older power plants.

After each turn, the computer counts the amount of energy produced by the power plants on the board and adds it to the total score.

Vasya already knows the types of power plant he will be able to build each turn. Now he wants to know, what the maximum possible score he can get is. Can you help him?

输入格式

The first line of the input contains one integer $n (1 \le n \le 100 000)$ -- the number of slots on the board. The second line contains the string $s$ . The i-th character of the string is $1$ if you can build one-slot power plant at the i-th turn and the character is $2$ if you can build two-slot power plant at the i-th turn. The number of turns does not exceed $100 000$ .

输出格式

The output should contain a single integer -- the maximal score that can be achieved.

题目大意

Vasya 正在玩一款新的电脑游戏 Energy Tycoon

游戏的规则非常简单：

有一行 $n$ 个空位。

有一些能源装置，每个能源装置会占用 $1$ 或 $2$ 个相邻的空位，并且每回合产生一个单位的能量。

在游戏里，每个回合可以建造一个新的能源装置（也可以不建造）。如果没有地方建新的能源装置，可以拆除一些旧的能源装置。

每一回合过后，电脑会统计这一回合内所有已经建造的能源装置产生的能量，并将其加到总分中。

Vasya 已经知道了每个回合他可以建造的能源装置的类型。现在他想知道，他能得到的最大分数是多少。你能帮他吗?

3
21121

10

2
12

2

2
211

4

提示

Time limit: 2 s, Memory limit: 256 MB.