Енергетичний магнат
Маленький Вася грає в нову комп'ютерну гру — покрокову стратегію "Енергетичний магнат".
Правила гри досить прості:
Ігрова дошка складається з n слотів, розташованих в ряд.
Є набір електростанцій, кожна з яких займає один або два сусідні слоти і виробляє одну одиницю енергії.
Кожен хід гри дозволяє побудувати одну нову електростанцію, яку можна розмістити на дошці в будь-якому місці на ваш розсуд. Якщо для нової електростанції немає місця, ви можете видалити деякі старі електростанції.
Після кожного ходу комп'ютер обчислює кількість енергії, що виробляється електростанціями на дошці, і додає її до загальної кількості очок у грі.
Вася вже знає всі типи електростанцій, які він зможе побудувати на кожному кроці гри. Він хоче дізнатися, яку максимальну кількість очок він зможе отримати в грі. Чи можете ви йому допомогти?
Вхідні дані
Перша строка містить число n (1 ≤ n ≤ 10^5) — кількість слотів на дошці. Друга строка містить рядок s. i-ий символ рядка дорівнює 1, якщо ви можете побудувати однослотову електростанцію в i-му раунді, і символ 2, якщо ви можете побудувати двослотову електростанцію в i-му раунді. Кількість раундів у грі не перевищує 10^5.
Вихідні дані
Виведіть одне число — найбільшу кількість очок, яку можна досягти.