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

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

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

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

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

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

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

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