|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||256 MB||16||9||8||61.538%|
Little Vasya is playing a new computer game — turn-based strategy “Energy Tycoon”.
The rules of the game are quite simple:
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 ≤ 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.
The output should contain a single integer — the maximal score that can be achieved.