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 10^6.


-----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.

Difficulty: interview

Starter code:

Solutions:
s = input()

cur_len = 1
a = []
char = []
for i in range(1, len(s)):
    if s[i] == s[i-1]: cur_len += 1
    else:
      a.append(cur_len)
      char.append(s[i-1])
      cur_len = 1
      
a.append(cur_len)
char.append(s[len(s)-1])

ans = 0
while len(a) > 1:
    n = len(a)
    inner_min = 100000000
    for i in range(1,n-1):
        if a[i] < inner_min: inner_min = a[i]
        
    k = min(a[0], a[n-1],(inner_min + 1)//2)
    #print("a: ", a, "; k = ", k)
    b = []
    new_char = []
    for i in range(n):
        if i == 0 or i == n-1:
            if a[i] > k:
                b.append(a[i]-k)
                new_char.append(char[i])
        else:
            if a[i] > 2*k:
                b.append(a[i] - 2*k)
                new_char.append(char[i])
##    print(b)
    ans += k
    if len(b) > 1:
        c = [0]*n
        newnew_char = [new_char[0]]
        count = 0
    
        for i in range(0,len(b)-1):
            c[count] += b[i]
            if new_char[i] == new_char[i+1]: continue
            else:
                count += 1
                newnew_char.append(new_char[i+1])
        if new_char[len(b)-2] == new_char[len(b) - 1]: c[count] += b[len(b)-1]
        else:
            #count += 1
            newnew_char.append(new_char[i+1])
            c[count] = b[len(b)-1]
        a = c[:count+1]
        char = newnew_char[:]
    else:
        a = b[:]

print(ans)
        


name = input()

blocks = []
now = name[0]
counter = 1
for x in range(1, len(name)):
    if name[x] != now:
        blocks.append((now, counter))
        now = name[x]
        counter = 1
    else:
        counter += 1
blocks.append((now, counter))

counter = 0
temp = []
while len(blocks) > 1:
    counter += 1
    temp = []
    (x, y) = blocks[0]
    if y > 1:
        temp.append((x, y - 1))
    for s in range(1, len(blocks) - 1):
        (x, y) = blocks[s]
        if len(temp) > 0:
            (tempx, tempy) = temp[-1]
            if y > 2:
                if x != tempx:
                    temp.append((x, y - 2))
                else:
                    temp[-1] = (x, tempy + y - 2)
        else:
            if y > 2:
                temp.append((x, y - 2))

    (x, y) = blocks[-1]
    if len(temp) > 0:
        (tempx, tempy) = temp[-1]
        if y > 1:
            if x != tempx:
                temp.append((x, y - 1))
            else:
                temp[-1] = (x, tempy + y - 1)
    else:
        if y > 1:
            temp.append((x, y - 1))
    blocks = temp

print(counter)


import sys
sys.setrecursionlimit(1000000)
read = sys.stdin.readline

points = read().strip()

lst = [[points[0], 1]]

for p in points[1:]:
    if p == lst[-1][0]:
        lst[-1][1] += 1
    else:
        lst += [[p, 1]]
ans = 0
while len(lst) > 1:
    ans += 1
    tmp = []
    if lst[0][1] > 1:
        tmp.append([lst[0][0], lst[0][1]-1])
    for i in lst[1:-1]:
        if i[1] > 2:
            if len(tmp) == 0 or tmp[-1][0] != i[0]:
                tmp.append([i[0], i[1]-2])
            else:
                tmp[-1][1] += i[1] - 2
    if lst[-1][1] > 1:
        if len(tmp) == 0 or lst[-1][0] != tmp[-1][0]:
            tmp.append([lst[-1][0], lst[-1][1]-1])
        else:
            tmp[-1][1] += lst[-1][1]-1
    lst = tmp

print(ans)

import sys
from collections import defaultdict as di
color = input()
n = len(color)

lnei = [-1]*n
rnei = [-1]*n
to_be_deleted = []
deleted = [False]*n
iters = 0

for i in range(n):
    if i-1>=0:
        lnei[i]=i-1
        if color[i]!=color[i-1]:
            to_be_deleted.append(i)
    if i+1<n:
        rnei[i]=i+1
        if color[i]!=color[i+1]:
            to_be_deleted.append(i)

if len(to_be_deleted)==0:
    print(0)
    return

while True:
    was_deleted = False

    pot_sui = []
    for node in to_be_deleted:
        if deleted[node]:
            continue
        was_deleted=True
        deleted[node]=True
        
        if rnei[node]!=-1:
            lnei[rnei[node]]=lnei[node]
            pot_sui.append(rnei[node])

        if lnei[node]!=-1:
            rnei[lnei[node]]=rnei[node]
            pot_sui.append(lnei[node])
    
    
    to_be_deleted=[]
    for node in pot_sui:
        if deleted[node]:
            continue
        if lnei[node]!=-1 and color[node]!=color[lnei[node]]:
            to_be_deleted.append(node)
        elif rnei[node]!=-1 and color[node]!=color[rnei[node]]:
            to_be_deleted.append(node)
    if not was_deleted:
        break
    iters += 1

print(iters)


s = input()
n = 1
    
for i in range(1, len(s)):
  if s[i] != s[i-1]:
    n += 1

mas = [0] * n
col = [0] * n

count = 1
idx = 0
c = s[0]
for i in range(1, len(s)):
  if s[i] == s[i-1]:
    count += 1
  else:
    mas[idx] = count
    col[idx] = c
    idx += 1
    count = 1
    c = s[i]
    
mas[idx] = count
col[idx] = c

res = 0

while n > 1:
  newlen = n
  idx = -1
      
  for i in range(0, n):
    if (i == 0) or (i == n - 1):
      mas[i] -= 1
    elif mas[i] >= 2:
      mas[i] -= 2
    else:
      mas[i] = 0
      
    if mas[i] == 0:
      newlen -= 1
    else:
      if idx >= 0 and col[idx] == col[i]:
        mas[idx] += mas[i]
        newlen -= 1
      else:
        idx += 1
        mas[idx] = mas[i]
        col[idx] = col[i] 
        type = i % 2
        
  n = newlen
  res += 1

print(res)

s=input()
a=[[s[0],1]]

for i in s[1:]:
    if(a[-1][0]==i):
        a[-1][1]+=1
    else:
        a.append([i,1])
turns=0
while((len(a)>1)):
    turns+=1
    temp=[]
    if(a[0][1]>1):
        temp.append([a[0][0],a[0][1]-1])
    for i in a[1:-1]:
        if(i[1]>2):
            temp.append([i[0],i[1]-2])
    if(a[-1][1]>1):
        temp.append([a[-1][0],a[-1][1]-1])
    if(len(temp)<2):
        break
    a=[temp[0],]
    for i in temp[1:]:
        if(i[0]!=a[-1][0]):
            a.append(i)
        else:
            a[-1][1]+=i[1]
print(turns)

s=input()
a=[[s[0],1]]

for i in s[1:]:
    if(a[-1][0]==i):
        a[-1][1]+=1
    else:
        a.append([i,1])
turns=0
while((len(a)>1)):
    turns+=1
    temp=[]
    if(a[0][1]>1):
        temp.append([a[0][0],a[0][1]-1])
    for i in a[1:-1]:
        if(i[1]>2):
            temp.append([i[0],i[1]-2])
    if(a[-1][1]>1):
        temp.append([a[-1][0],a[-1][1]-1])
    if(len(temp)<2):
        break
    a=[temp[0],]
    for i in temp[1:]:
        if(i[0]!=a[-1][0]):
            a.append(i)
        else:
            a[-1][1]+=i[1]
print(turns)

s=input()
a=[[s[0],1]]

for i in s[1:]:
    if(a[-1][0]==i):
        a[-1][1]+=1
    else:
        a.append([i,1])
turns=0
while((len(a)>1)):
    turns+=1
    temp=[]
    if(a[0][1]>1):
        temp.append([a[0][0],a[0][1]-1])
    for i in a[1:-1]:
        if(i[1]>2):
            temp.append([i[0],i[1]-2])
    if(a[-1][1]>1):
        temp.append([a[-1][0],a[-1][1]-1])
    if(len(temp)<2):
        break
    a=[temp[0],]
    for i in temp[1:]:
        if(i[0]!=a[-1][0]):
            a.append(i)
        else:
            a[-1][1]+=i[1]
print(turns)

# https://codeforces.com/problemset/problem/909/D
def process(a):
    assert len(a) >= 2
    
    n    = len(a)
    min_ = float('inf')

    for i, [cnt, c] in enumerate(a):
        if i == 0 or i == n-1:
            min_ = min(min_, cnt)
        else:
            min_ = min(min_, (cnt+1) //2) 
    
    b    = []
    for i, [cnt, c] in enumerate(a):
        if i == 0 or i == n-1:
            remain = cnt - min_
        else:
            remain = cnt - min_ * 2
        
        if remain <= 0:
            continue
        
        if len(b) == 0 or c != b[-1][1]:
            b.append([remain, c])
        else:
            pre_cnt, pre_c  = b.pop()
            b.append([pre_cnt+remain, c])
    
    return b, min_        

S   = input() + ' '
cur = []

cnt = 0
pre = ''
for x in S:
    if cnt == 0:
        cnt+= 1
        pre = x
    elif x!=pre:
        cur.append([cnt, pre])
        cnt = 1
        pre = x
    else:
        cnt+=1

cnt = 0
while len(cur) not in [0, 1]: 
    cur, min_ = process(cur)
    cnt+=min_
    
print(cnt)