Թաքցված խնդիր
|Այս խնդիրը թաքցված է խմբագրական խրհրդի անդամի կողմից քանի որ կամ այն ոչ ճիշտ լեզվով է գրված,|կամ թեստային տվյալներն են սխալ, կամ խնդրի ձևակերպումը պարզ չէ։|

ACM_0010 - ENERGY TYCOON

  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?

Input

  The first line of the input contains one integer n (1 n 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.

Output

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

Examples

stdin

stdout

1

3

21121

 10

2

2

12

 2

The picture shows the optimal sequence of moves for the first example.


Ավելացրեց.Հրանտ Հովհաննիսյան
Ամսաթիվ.2013-12-04
Ժամանակի սահմանափակումը.1s
Ծրագրի տեքստի սահմանափակումը.50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Լեզուներ.Բոլորը բացի ASM32 ASM64 GAWK CLPS CLOJURE D ERL FSHARP FORTRAN GOSU HASK ICON ICK NEM NIM OBJC-CLANG PICO PIKE PYPY PYPY3 PY_NBC RUST SCM guile CHICKEN SED TCL WHITESPACE
Աղբյուրը.Northern QF 2013.E

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.