e-olymp
Задачи

Энергетический магнат

Энергетический магнат

Маленький Вася играет в новую компьютерную игру - пошаговую стратегию "Энергетический магнат".

Правила игры достаточно просты:

  • Доска содержит n слотов, расположенных в линию.
  • Имеется набор электростанций, каждая из которых занимает один или два слота подряд, и производит одну единицу энергии.
  • Каждый ход игры позволяет построить одну новую электростанцию, ее можно расположить на доске в любом месте по Вашему усмотрению. Если для новой электростанции нет места, Вы можете удалить некоторые старые электростанции.
  • После выполнения каждого хода компьютер вычисляет количество энергии, производимой расположенными на доске электростанциями, и добавляет его к общему количеству очков в игре.

prb6264

Вася уже знает все типы электростанций, которые он сможет построить на каждом шаге игры. Он хочет знать, какое максимальное количество очков он сможет получить в игре. Можете ли Вы ему помочь?

Входные данные

Первая строка содержит число n (1n100000) - количество слотов на доске. Вторая строка содержит строку s. i-ый символ строки равен 1, если Вы можете построить однослотовую электростанцию в i-ом раунде, и символ 2, если Вы можете построить двуслотовую электростанцию в i-ом раунде. Количество раундов в игре не превосходит 100000.

Выходные данные

Вывести одно число - наибольшее количество очков, которое можно достичь.

Лимит времени 1 секунды
Лимит использования памяти 256 MiB
Входные данные #1
3
21121
Выходные данные #1
10
Входные данные #2
2
12
Выходные данные #2
2
Входные данные #3
2
211
Выходные данные #3
4

Объяснение: The picture shows the optimal sequence of moves for the first example.

Источник 2013 ACM NEERC, Northern Subregion, Санкт-Петербург, Октябрь 26