Энергетический магнат
Энергетический магнат
Маленький Вася играет в новую компьютерную игру - пошаговую стратегию "Энергетический магнат".
Правила игры достаточно просты:
- Доска содержит n слотов, расположенных в линию.
- Имеется набор электростанций, каждая из которых занимает один или два слота подряд, и производит одну единицу энергии.
- Каждый ход игры позволяет построить одну новую электростанцию, ее можно расположить на доске в любом месте по Вашему усмотрению. Если для новой электростанции нет места, Вы можете удалить некоторые старые электростанции.
- После выполнения каждого хода компьютер вычисляет количество энергии, производимой расположенными на доске электростанциями, и добавляет его к общему количеству очков в игре.
Вася уже знает все типы электростанций, которые он сможет построить на каждом шаге игры. Он хочет знать, какое максимальное количество очков он сможет получить в игре. Можете ли Вы ему помочь?
Входные данные
Первая строка содержит число n (1 ≤ n ≤ 105
) - количество слотов на доске. Вторая строка содержит строку s. i-ый символ строки равен 1, если Вы можете построить однослотовую электростанцию в i-ом раунде, и символ 2, если Вы можете построить двуслотовую электростанцию в i-ом раунде. Количество раундов в игре не превосходит 105
.
Выходные данные
Вывести одно число - наибольшее количество очков, которое можно достичь.
3 21121
10
2 12
2
2 211
4
Объяснение: The picture shows the optimal sequence of moves for the first example.