Energy Tycoon

Interview

Time limit2sMemory limit256 MB

Summary

Place each offered one-slot or two-slot plant on an n-slot board, removing blocking plants when full, to maximize the total plant count summed over all turns.

Level: Medium5 of 10
Topics: Greedy, Simulation
Solved: No attempts yet

Problem

Vasya is playing a turn-based strategy game called Energy Tycoon.

The rules are simple.

The board has $n$ slots in a row.
A power plant occupies one or two consecutive slots and produces one unit of energy.
Every turn the game offers one new power plant, and you can place it on the board if you want to. If there is no room for it, you can remove any of the plants you built earlier.
At the end of every turn, the game adds the energy produced by the plants standing on the board to the total score.

Vasya already knows which power plant he can build on each turn. What is the largest total score he can reach?

Input

The first line contains the number of slots $n$ ( $1 \le n \le 100000$ ).

The second line contains a string $s$ . If the $i$ -th character of $s$ is 1, you can build a one-slot power plant on turn $i$ , and if it is 2, you can build a two-slot power plant on turn $i$ . The number of turns does not exceed 100000.

Output

Print the largest total score that can be achieved.

Examples3

Example 1
Input
```
3
21121
```
Expected output
```
10
```
Example 2
Input
```
2
12
```
Expected output
```
2
```
Example 3
Input
```
2
211
```
Expected output
```
4
```