[Round#455 Div2] D. Colorful Points

http://codeforces.com/problemset/problem/909/D

D. Colorful Points

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a set of points on a straight line. Each point has a color assigned to it. For point a, its neighbors are the points which don't have any other points between them and a. Each point has at most two neighbors - one from the left and one from the right.

You perform a sequence of operations on this set of points. In one operation, you delete all points which have a neighbor point of a different color than the point itself. Points are deleted simultaneously, i.e. first you decide which points have to be deleted and then delete them. After that you can perform the next operation etc. If an operation would not delete any points, you can't perform it.

How many operations will you need to perform until the next operation does not have any points to delete?

Input

Input contains a single string of lowercase English letters 'a'-'z'. The letters give the points' colors in the order in which they are arranged on the line: the first letter gives the color of the leftmost point, the second gives the color of the second point from the left etc.

The number of the points is between 1 and 106.

Output

Output one line containing an integer - the number of operations which can be performed on the given set of points until there are no more points to delete.

Examples

input

aabb

output

2

input

aabcaa

output

1

Note

In the first test case, the first operation will delete two middle points and leave points "ab", which will be deleted with the second operation. There will be no points left to apply the third operation to.

In the second test case, the first operation will delete the four points in the middle, leaving points "aa". None of them have neighbors of other colors, so the second operation can't be applied.

---

문자열이 주어졌을 때, 문자열의 길이를 L이라고 하면 최대 L번만큼의 스캔을 진행하며 문자를 삭제한다.

매 스캔시 인접한 양옆의 문자중 하나라도 다른 문자가 있는 문자들을 삭제되는 방식으로 진행된다.

이렇게 스캔을 진행 했을 때, 최대 몇번의 스캔을 진행할 수 있는지(더이상 삭제할 문자가 없는지)를 묻는 문제이다.

매번 문자를 하나씩 살펴본다면 당연히 매 스캔시 최대 L개의 문자를 살펴봐야하므로 시간복잡도는 L^2 가 된다.

하지만, 동일한 부분문자열을 하나의 그룹으로 묶어서 생각해 본다면 스캔 횟수를 단축(압축?)시킬 수 있다.

예를들어 aaaabbcccddd 인 문자열이 주어진다면 a(4), b(2), c(3), d(3) 으로 표현할 수 있다. (괄호안의 숫자는 연속된 문자의 개수)

괄호안의 숫자를 그룹의 크기라 하면, 주어진 그룹들의 크기중 최소 크기만큼의 스캔이 진행되어야 문자열에 변화가 생긴다.

여기서 변화라고 함은 인접한 문자가 바뀌는 현상을 의미한다. 

즉, 위 예제에선 2번의 스캔이 지나야 b그룹이 사라지므로 사라진 그룹의 앞뒤 그룹의 인접한 문자가 b에서 각각 c와 a로 바뀌게된다.

aaaabbcccddd -> aacd

따라서 각 그룹의 크기를 매번 계산해 최소인 그룹의 크기를 찾아 

1. 각 그룹의 크기를 줄여주고

2. 크기가 0이되는 그룹은 삭제

3. 삭제 후 새로 인접한 그룹이 같은 문자라면 하나로 병합해주는 작업을 반복해 주면 문제를 해결할 수 있다.

얼핏보면 그룹의 개수가 L개, 탐색하는데 드는 횟수도 L이라 L^2처럼 보이지만 그룹의 크기가 동일한 그룹들은 한번의 탐색으로 삭제된다는 점을 생각해보면 시간복잡도는 O(L)이 됨을 계산할 수 있다