D. Разноцветные точки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан набор разноцветных точек на прямой. Две точки считаются соседними, если между ними нет других точек. У каждой точки может быть не более двух соседних — одна слева и одна справа.

Вы выполняете последовательность действий над этим набором. За одно действие вы удаляете все точки a, у которых есть соседняя точка цвета, отличного от цвета точки a. Все точки удаляются одновременно, т.е. сначала вы определяете, какие точки следует удалить, и затем удаляете их. После этого вы выполняете следующее действие и т.д. Если действие не удалит ни одной точки, его невозможно выполнить.

Сколько действий можно будет выполнить на заданном наборе точек так, чтобы каждое из них удалило хотя бы одну точку?

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

Входные данные состоят из единственной строки строчных латинских букв. Буквы задают цвета точек в том порядке, в котором они расположены на прямой: первая буква задает цвет самой левой точки, вторая — цвет второй слева точки и т.д.

Строка содержит от 1 до 106 букв.

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

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

Примеры
Входные данные
aabb
Выходные данные
2
Входные данные
aabcaa
Выходные данные
1
Примечание

В первом примере первое действие удалит две средние точки и оставит точки "ab", которые затем удалит второе действие. После этого не останется точек, над которыми можно было бы выполнить третье действие.

Во втором примере первое действие удалит четыре средние точки и оставит точки "aa". Ни у одной из них нет соседних точек другого цвета, поэтому второе действие невозможно выполнить.