Problem Description

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, each occupying one or two consecutive slots, and producing one unit of energy.

Each turn, the game allows you to build one new power plant. You can place 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 plants 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?

Input Format

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 a string $s$. The $i$-th character of the string is 1 if you can build a one-slot power plant at the $i$-th turn, and the character is 2 if you can build a two-slot power plant at the $i$-th turn. The number of turns does not exceed $100,000$.

Output Format

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

Sample Input and Output

Sample Input #1

3
21121

Sample Output #1

10

Sample Input #2

2
12

Sample Output #2

2

Sample Input #3

2
211

Sample Output #3

4

Notes/Hints

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

见题面 Input 部分

见题面 Output 部分