Задача 43. Свободный стих ≡

Условие

Сладкозвучная богиня,

Рифма золотая,

Слух чарует, стих созвучьем

Звонким замыкая.

И капризна, и лукава,

Вечно убегает.

Гений сам порой не сразу

Резвую поймает.

...

Фёдор Сологуб, "Рифма", 1880 г.

Катрен — четверостишие, рифмованная строфа в четыре строки. Схем рифмовки у катрена три: попарная aabb, перекрестная abab и опоясывающая abba.

Терцет — трёхстишие, строфа из трех строк. Схема рифмовки у терцета одна: aaa или bbb (все строки имеют одну рифму).

Вдохновлённый визитом музы, начинающий поэт Фёдор написал n строк с рифмами двух типов: a и b. Теперь ему необходимо оформить их в строфы вида катрен и терцет. Фёдор не согласен менять свои строки местами, но не возражает против замены строки с рифмы a на рифму b и наоборот. Какое наименьшее количество замен ему необходимо будет сделать, чтобы справиться с задачей? Каждая строфа должна иметь длину 3 или 4 и соответствовать одной из схем рифмовки.

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

Первая строка входного файла содержит натуральное число n — количество придуманных Фёдором строк. Во второй строке расположена строка длины n, состоящая из символов a и b — описание типов строк.

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

Выведите одно неотрицательное целое число — ответ на вопрос задачи.

Ограничения

6 ≤ n ≤ 10⁵

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

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при n ≤ 10, получат не менее 20 баллов.

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

В примере дано n = 14 (Фёдор написал 14 строк, которые описываются рифмами ababbabbababaa). Этот набор необходимо разбить на части, каждая из которых может быть одного из 5 видов: aabb, abab, abba, aaa, bbb, сделав как можно меньше замен в исходной строке.

Это можно сделать всего с тремя заменами, получив, например, строку ababbbbbbbabab. Теперь строку можно разбить на подстроки разрешённого типа: abab bbb bbb abab. Меньшим количеством замен обойтись не получится.

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

14
ababbabbababaa

3