Фермер Джон пытается сделать совершенную фотографию своих \(N\) коров
(\(2 \leq N \leq 2\cdot 10^5\), \(N\) четное).
У ФД есть коровы двух пород Guernseys и Holsteins.
Чтобы сделать свою фотографию как можно более эстетичной, он хочет
выстроить своих коров так, чтобы как можно больше коров породы Guernseys
находились на позициях с чётными номерами (первая позиция в ряду - нечётная,
следующая чётная и т.д.). Для перестройки порядка коров он может только
попросить "префикс" своих коров четной длины сделать реверс.
"Префикс" состоит из диапазона коров от первой коровы до \(j\)-ой коровы для
некоторой позиции \(j\).
Вычислите минимальное количество реверсов, которое потребуется ФД
для достижения своей цели.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка ввода содержит величину
\(N\).
Вторая строка ввода содержит набор символов длины \(N\), указывающих
начальный порядок коров слева направо. Символ 'H' представляет породу Holstein,
а символ 'G' представляет породу Guernsey.
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите минимальное количество реверсов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
14
GGGHGHHGHHHGHG
|
1
|