给你一组直线上的点。每个点都分配有一种颜色。对于点 a,它的邻居是与 a 之间没有任何其他点的点。每个点至多有两个邻居 - 一个来自左侧,一个来自右侧。
您对这组点执行一系列操作。在一项操作中,您可以删除具有与该点本身颜色不同的相邻点的所有点。点是同时删除的,即首先您决定必须删除哪些点,然后删除它们。之后您可以执行下一个操作等。如果操作不会删除任何点,则无法执行它。
您需要执行多少次操作,直到下一个操作没有任何要删除的点?
输入
输入包含一个由小写英文字母“a”-“z”组成的字符串。这些字母按照点在线上排列的顺序给出点的颜色:第一个字母给出最左边点的颜色,第二个字母给出左边第二个点的颜色,等等。
点数在 1 到 106 之间。
输出
输出一行包含一个整数 - 可以对给定的一组点执行的操作数,直到没有更多的点可以删除。
示例
输入 #1
aabb
输出 #1
2
输入 #2
aabcaa
输出 #2
1
注意
在第一个测试用例中,第一个操作将删除两个中间点并留下点“ab”,第二个操作将删除该点。将没有剩余点可以应用第三次操作。
在第二个测试用例中,第一个操作将删除中间的四个点,留下点“aa”。它们都没有其他颜色的邻居,因此无法应用第二个操作。