Задача 98D. Конкурс ТИК ≡

Условие

Тимофей очень любит участвовать в разнообразных игровых конкурсах для школьников. "Китайская панда — иероглифы для всех", "Кентавр", "Французский пудель", "Золотой урон", "Сумчатое — аборигенам" — он не пропускает ни одного. Но особенно Тимофею нравится конкурс по технологии информационной коммуникации (ТИК).

Участникам конкурса ТИК предлагается ответить на n вопросов. На каждый вопрос предлагается четыре варианта ответа, обозначенных буквами a, b, c и d. Участник выбирает один из вариантов и отмечает его крестиком в поле для ответа. Правильный ответ на вопрос приносит конкурсанту один балл, неправильный — ноль баллов. Всего в конкурсе можно набрать от 0 до n баллов.

Вот и настал день проведения долгожданного конкурса. Одна беда — именно сейчас Тимофею нужно срочно убегать по очень важным делам. Поэтому он заполнил клеточки крестиками, совершенно не вчитываясь в задания. Делал он это в соответствии с собственной Стратегией: поставил случайным образом крестик в поле для ответа на первый вопрос, а каждый следующий крестик ставил на одну позицию выше или ниже предыдущего. Ниже приведен пример заполнения поля для ответов в соответствии со Стратегией.

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

Формат входных данных

В первой строке входного файла записано одно натуральное число n — количество вопросов.

Во второй строке записаны верные ответы на вопросы конкурса — строка из n символов. На каждой позиции в строке стоит одна из четырех букв: a, b, c или d.

Формат выходных данных

В единственной строке выходного файла запишите одно натуральное число — максимальное количество баллов, которое может набрать Тимофей в соответствии со Стратегией.

Ограничения

1 ≤ n ≤ 10⁵

Система оценки и описание подзадач

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.

Подзадача 1: n = 2, баллы: 15.

Подзадача 2: n ≤ 8, баллы: 30.

Подзадача 3: нет дополнительных ограничений, баллы: 55.

Пояснения к примерам

Комментарий к первому примеру:

Единственный вариант заполнения в соответствии со Стратегией, который даст возможность Тимофею получить 3 балла из 4: baba.

Комментарий ко второму примеру:

Один из вариантов заполнения в соответствии со Стратегией, который даст возможность Тимофею получить 3 балла из 8: abcbabcb. Больше 3 баллов набрать невозможно.

Примеры тестов

4
daba

3

8
adbcaadb

3