Вам дан набор разноцветных точек на прямой. Две точки считаются соседними, если между ними нет других точек. У каждой точки может быть не более двух соседних — одна слева и одна справа.
Вы выполняете последовательность действий над этим набором. За одно действие вы удаляете все точки a, у которых есть соседняя точка цвета, отличного от цвета точки a. Все точки удаляются одновременно, т.е. сначала вы определяете, какие точки следует удалить, и затем удаляете их. После этого вы выполняете следующее действие и т.д. Если действие не удалит ни одной точки, его невозможно выполнить.
Сколько действий можно будет выполнить на заданном наборе точек так, чтобы каждое из них удалило хотя бы одну точку?
Выходные данные
Выведите одно число — количество действий, которые можно выполнить на заданном наборе точек так, чтобы каждое действие удалило хотя бы одну точку.
Примечание
В первом примере первое действие удалит две средние точки и оставит точки "ab", которые затем удалит второе действие. После этого не останется точек, над которыми можно было бы выполнить третье действие.
Во втором примере первое действие удалит четыре средние точки и оставит точки "aa". Ни у одной из них нет соседних точек другого цвета, поэтому второе действие невозможно выполнить.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
aabb
|
2
|
|
2
|
aabcaa
|
1
|