Задача №111887. Energy Tycoon

Вася играет в новую пошаговую стратегию «Energy Tycoon».

Правила этой игры просты:

  • Доска для игры представляет из себя линию из \(n\) клеток
  • Есть электростанции, одна электростанция занимает одну или две соседних клетки и производит одну единицу энергии.
  • В каждом ходу можно построить одну новую электростанцию, Вы можете поместить её на свободное место на доске, если хотите. Если свободного места нет, можно убрать с доски ранее построенные электростанции.
  • После каждого хода к результату прибавляется количество энергии, вырабатываемое всеми станциями на поле.

      • Вася уже знает типы электростанций, которые он сможет построить на каждом ходу. Теперь он хочет узнать какое максимальное количество очков он сможет набрать.

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

Первая строка входного файла содержит одно целое число \(n\) (\(1 \leq n \leq 100000\)) – количество клеток на доске.

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

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

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

Примеры
Входные данные
3
21121
Выходные данные
10
Входные данные
2
12
Выходные данные
2
Сдать: для сдачи задач необходимо войти в систему