Энергетический магнат
Маленький Вася играет в новую компьютерную игру - пошаговую стратегию "Энергетический магнат".
Правила игры достаточно просты:
Доска содержит n слотов, расположенных в линию.
Имеется набор электростанций, каждая из которых занимает один или два слота подряд, и производит одну единицу энергии.
Каждый ход игры позволяет построить одну новую электростанцию, ее можно расположить на доске в любом месте по Вашему усмотрению. Если для новой электростанции нет места, Вы можете удалить некоторые старые электростанции.
После выполнения каждого хода компьютер вычисляет количество энергии, производимой расположенными на доске электростанциями, и добавляет его к общему количеству очков в игре.
Вася уже знает все типы электростанций, которые он сможет построить на каждом шаге игры. Он хочет знать, какое максимальное количество очков он сможет получить в игре. Можете ли Вы ему помочь?
Входные данные
Первая строка содержит число n (1 ≤ n ≤ 10^5) - количество слотов на доске. Вторая строка содержит строку s. i-ый символ строки равен 1, если Вы можете построить однослотовую электростанцию в i-ом раунде, и символ 2, если Вы можете построить двуслотовую электростанцию в i-ом раунде. Количество раундов в игре не превосходит 10^5.
Выходные данные
Вывести одно число - наибольшее количество очков, которое можно достичь.