A schoolboy named Vasya loves reading books on programming and mathematics. He has recently read an encyclopedia article that described the method of median smoothing (or median filter) and its many applications in science and engineering. Vasya liked the idea of the method very much, and he decided to try it in practice.

Applying the simplest variant of median smoothing to the sequence of numbers a_1, a_2, ..., a_{n} will result a new sequence b_1, b_2, ..., b_{n} obtained by the following algorithm:  b_1 = a_1, b_{n} = a_{n}, that is, the first and the last number of the new sequence match the corresponding numbers of the original sequence.  For i = 2, ..., n - 1 value b_{i} is equal to the median of three values a_{i} - 1, a_{i} and a_{i} + 1. 

The median of a set of three numbers is the number that goes on the second place, when these three numbers are written in the non-decreasing order. For example, the median of the set 5, 1, 2 is number 2, and the median of set 1, 0, 1 is equal to 1.

In order to make the task easier, Vasya decided to apply the method to sequences consisting of zeros and ones only.

Having made the procedure once, Vasya looked at the resulting sequence and thought: what if I apply the algorithm to it once again, and then apply it to the next result, and so on? Vasya tried a couple of examples and found out that after some number of median smoothing algorithm applications the sequence can stop changing. We say that the sequence is stable, if it does not change when the median smoothing is applied to it.

Now Vasya wonders, whether the sequence always eventually becomes stable. He asks you to write a program that, given a sequence of zeros and ones, will determine whether it ever becomes stable. Moreover, if it ever becomes stable, then you should determine what will it look like and how many times one needs to apply the median smoothing algorithm to initial sequence in order to obtain a stable one.


-----Input-----

The first input line of the input contains a single integer n (3 ≤ n ≤ 500 000) — the length of the initial sequence.

The next line contains n integers a_1, a_2, ..., a_{n} (a_{i} = 0 or a_{i} = 1), giving the initial sequence itself.


-----Output-----

If the sequence will never become stable, print a single number  - 1.

Otherwise, first print a single integer — the minimum number of times one needs to apply the median smoothing algorithm to the initial sequence before it becomes is stable. In the second line print n numbers separated by a space  — the resulting sequence itself.


-----Examples-----
Input
4
0 0 1 1

Output
0
0 0 1 1

Input
5
0 1 0 1 0

Output
2
0 0 0 0 0



-----Note-----

In the second sample the stabilization occurs in two steps: $01010 \rightarrow 00100 \rightarrow 00000$, and the sequence 00000 is obviously stable.

Difficulty: competition

Starter code:

Solutions:
from sys import stdin

#stdin = open('input.txt')

n = int(stdin.readline())

seq = [int(x) for x in stdin.readline().split()]
carry = seq[0]
result = [carry]

mark = False
cur_len = 0
max_len = 0

i = 1
while i < len(seq) - 1:
    if mark:
        if seq[i] != seq[i + 1]:
            cur_len += 1
        else:
            if cur_len > max_len:
                max_len = cur_len

            if seq[i] == carry:
                result.extend([carry]*cur_len)
            else:
                result.extend([carry]*(cur_len//2))
                result.extend([seq[i]]*(cur_len//2))

            result.append(seq[i])
            mark = False
            cur_len = 0
    elif seq[i] != seq[i - 1] and seq[i] != seq[i + 1]:
        mark = True
        cur_len = 1
        carry = seq[i - 1]
    else:
        result.append(seq[i])

    i += 1

if mark:
    if cur_len > max_len:
            max_len = cur_len

    if seq[i] == carry:
        result.extend([carry]*cur_len)
    else:
        result.extend([carry]*(cur_len//2))
        result.extend([seq[i]]*(cur_len//2))

result.append(seq[i])

print((max_len + 1)//2)
for x in result:
    print(x, end=' ')

from sys import stdin

#stdin = open('input.txt')

n = int(stdin.readline())

seq = stdin.readline().split()
carry = seq[0]
result = [carry]

mark = False
cur_len = 0
max_len = 0

i = 1
while i < len(seq) - 1:
    if mark:
        if seq[i] != seq[i + 1]:
            cur_len += 1
        else:
            if cur_len > max_len:
                max_len = cur_len

            if seq[i] == carry:
                result.extend([carry]*cur_len)
            else:
                result.extend([carry]*(cur_len//2))
                result.extend([seq[i]]*(cur_len//2))

            result.append(seq[i])
            mark = False
            cur_len = 0
    elif seq[i] != seq[i - 1] and seq[i] != seq[i + 1]:
        mark = True
        cur_len = 1
        carry = seq[i - 1]
    else:
        result.append(seq[i])

    i += 1

if mark:
    if cur_len > max_len:
            max_len = cur_len

    if seq[i] == carry:
        result.extend([carry]*cur_len)
    else:
        result.extend([carry]*(cur_len//2))
        result.extend([seq[i]]*(cur_len//2))

result.append(seq[i])

print((max_len + 1)//2)
for x in result:
    print(x, end=' ')

from sys import stdin

#stdin = open('input.txt')

n = int(stdin.readline())

seq = stdin.readline().split()
result = [0] * n
result[0] = seq[0]

mark = False
cur_len = 0
max_len = 0
carry = 0
carry_id = 0

i = 1
while i < len(seq) - 1:
    if mark:
        if seq[i] != seq[i + 1]:
            cur_len += 1
        else:
            if cur_len > max_len:
                max_len = cur_len

            if seq[i] == carry:
                #result.extend([carry]*cur_len)
                result[carry_id : i : 1] = [carry] * cur_len
            else:
                #result.extend([carry]*(cur_len//2))
                #result.extend([seq[i]]*(cur_len//2))
                result[carry_id : carry_id + cur_len//2 : 1] = [carry]*(cur_len//2)
                result[carry_id + cur_len//2 : i : 1] = [seq[i]]*(cur_len//2)

            result[i] = seq[i]
            mark = False
            cur_len = 0
    elif seq[i] != seq[i - 1] and seq[i] != seq[i + 1]:
        mark = True
        cur_len = 1
        carry = seq[i - 1]
        carry_id = i
    else:
        result[i] = seq[i]

    i += 1

if mark:
    if cur_len > max_len:
            max_len = cur_len

    if seq[i] == carry:
        #result.extend([carry]*cur_len)
        result[carry_id : i] = [carry]*cur_len
    else:
        #result.extend([carry]*(cur_len//2))
        #result.extend([seq[i]]*(cur_len//2))
        result[carry_id : carry_id + cur_len//2] = [carry]*(cur_len//2)
        result[carry_id + cur_len//2 : i] = [seq[i]]*(cur_len//2)

result[i] = seq[i]

print((max_len + 1)//2)
for x in result:
    print(x, end=' ')

N = int(input())
seq = [ i for i in input().split() ]

def end_lst(i):
    while i < N - 1 and seq[i] != seq[i + 1]:
        i = i + 1
    return i


def reorder(lst, start, end):
    if start == end - 1:
        return 0
    if lst[start] == lst[end]:
        for i in range(start, end + 1):
            lst[i] = lst[start]
        return (end - start) // 2

    mid = (start + end) // 2
    for i in range(start, mid + 1):
        lst[i] = lst[start]
    for i in range(mid + 1, end + 1):
        lst[i] = lst[end]
    return (end - start + 1) // 2 - 1

i, ans = 0, 0
while i < N - 1:
    if seq[i] != seq[i + 1]:
        end = end_lst(i)
        ans = max(reorder(seq, i, end), ans)
        i = end
    else:
        i += 1

print(ans)
print(" ".join(seq))

N = int(input())
seq = [ int(i) for i in input().split() ]

def end_lst(i):
    while i < N - 1 and seq[i] != seq[i + 1]:
        i = i + 1
    return i


def reorder(lst, start, end):
    if start == end - 1:
        return 0
    if lst[start] == lst[end]:
        for i in range(start, end + 1):
            lst[i] = lst[start]
        return (end - start) // 2

    mid = (start + end) // 2
    for i in range(start, mid + 1):
        lst[i] = lst[start]
    for i in range(mid + 1, end + 1):
        lst[i] = lst[end]
    return (end - start + 1) // 2 - 1

i, ans = 0, 0
while i < N - 1:
    if seq[i] != seq[i + 1]:
        end = end_lst(i)
        ans = max(reorder(seq, i, end), ans)
        i = end
    else:
        i += 1

print(ans)
seq = list(map(str, seq))
print(" ".join(seq))

def main():
    n, l = int(input()), input().split()
    x, a = [False] * n, l[0]
    for i, b in enumerate(l):
        if a == b:
            x[i] = x[i - 1] = True
        a = b
    b = 0
    for i, a in enumerate(x):
        if a:
            if b:
                if b & 1:
                    a = l[i]
                    for j in range(i - b, i):
                        l[j] = a
                else:
                    a = l[i - 1]
                    for j in range(i - b, i - b // 2 + 1):
                        l[j] = a
                    a = l[i]
                    for j in range(j, i):
                        l[j] = a
                b = 0
        else:
            b += 1
        x[i] = b
    print((max(x) + 1) // 2)
    print(' '.join(l))


def __starting_point():
    main()

__starting_point()

n = int(input())
a = list(map(int, input().split()))
a = [a[0]] + a[:] + [a[-1]]
b = a[:]
cur = 0
ans = 0
c1 = c2 = -1
for i in range(1, n + 2):
    if a[i] != a[i - 1]:
        if cur == 0:
            c1 = a[i - 1]
        cur += 1
        ans = max(ans, cur // 2)
    elif cur:
        c2 = a[i - 1]
        if cur % 2 == 0:
            for j in range(i - cur, i - 1):
                b[j] = c1
        else:
            mid = i - (cur // 2) - 1
            for j in range(i - cur, i - 1):
                b[j] = c1 if j < mid else c2
        cur = 0
print(ans)
print(*b[1:-1])


def mp():

    return list(map(int,input().split()))

def lt():

    return list(map(int,input().split()))

def pt(x):

    print(x)



n = int(input())

L = lt()

count = 0

i = 0

c = [None for i in range(n)]

while i < n-1:

    j = i

    while j < n-1 and L[j] != L[j+1]:

        j += 1

    span = j-i+1

    for k in range(i,i+span//2):

        c[k] = L[i]

    for k in range(i+span//2,j+1):

        c[k] = L[j]

    count = max(count,(span-1)//2)

    i = j+1

    if i == n-1:

        c[i] = L[i]

print(count)

print(' '.join([str(r) for r in c]))

    



# Made By Mostafa_Khaled


from sys import stdin
n=int(stdin.readline().strip())
s=list(map(int,stdin.readline().strip().split()))

l=0
flag=True
x=0
for i in range(1,n):
    if s[i]!=s[i-1]:
        if flag:
            flag=False
            l=i-1
    else:
        r=i-1
        if not flag:
            y=0
            yy=r-1
            for j in range(l+1,r):
                s[j]=s[j-1]
                y+=1
                s[yy]=s[yy+1]
                yy-=1
                if(yy<=j):
                    break
            x=max(x,y)
        flag=True

if True:
    if True:
        if not flag:
            y=0
            yy=n-2
            r=n-1
            for j in range(l+1,r):
                s[j]=s[j-1]
                y+=1

                s[yy]=s[yy+1]
                yy-=1
                if(yy<=j):
                    break
            x=max(x,y)
print(x)
print(*s)



from math import ceil

def __starting_point():
    n = int(input())
    arr = list(map(int, input().split()))

    narr = [True]

    for i in range(1, n - 1):
        x = arr[i]
        narr.append(x == arr[i - 1] or x == arr[i + 1])

    narr.append(True)

    cnt = 0
    mc = 0

    for x in narr:
        if not x:
            cnt += 1
        if x and cnt:
            mc = max(mc, cnt)
            cnt = 0

    if cnt:
        mc = max(mc, cnt)

    print(ceil(mc / 2))

    ss = None

    for i, x in enumerate(arr):
        if not narr[i]:
            if ss is None:
                ss = i
        elif ss is not None:
            if arr[ss - 1] == x:
                for j in range(ss, i):
                    arr[j] = x
            else:
                for j in range(ss, i):
                    arr[j] = arr[ss - 1] if j < (i + ss) / 2 else x
            ss = None

    print(*arr)

__starting_point()

import sys
input=sys.stdin.readline

n=int(input())
a=list(map(int,input().split()))
d=[]
e=[]
for i in range(1,n-1):
    if a[i]!=a[i-1] and a[i]!=a[i+1]:
        e.append([a[i],i])
    else:
        if e!=[]:
            d.append(e)
            e=[]
if e!=[]:
    d.append(e)
if len(d)==0:
    print(0)
    print(*a)
else:
    e=[]
    for i in range(len(d)):
        if d[i][0][0]==0:
            if len(d[i])%2==0:
                m=len(d[i])
                e.append(m//2)
                for j in range(m//2):
                    a[d[i][j][1]]=1
                    a[d[i][m-j-1][1]]=0
            else:
                m=len(d[i])
                e.append(m//2+1)
                for j in range(m):
                    a[d[i][j][1]]=1
        
        if d[i][0][0]==1:
            if len(d[i])%2==0:
                m=len(d[i])
                e.append(m//2)
                for j in range(m//2):
                    a[d[i][j][1]]=0
                    a[d[i][m-j-1][1]]=1
            else:
                m=len(d[i])
                e.append(m//2+1)
                for j in range(m):
                    a[d[i][j][1]]=0
    print(max(e))
    print(*a)

n = int(input())
a = list(map(int, input().split()))
r, b, c = 0, [a[0]], 0
for x, y, z in zip(a, a[1:], a[2:]):
    if x != y != z:
        c += 1
    else:
        if c & 1:
            b.extend([y]*(c+1))
        else:    
            b.extend([1-y]*(c//2) + [y]*(c//2+1))
        r = max(r, (c+1)//2)
        c = 0
y = a[-1]            
if c & 1:
    b.extend([y]*(c+1))
else:    
    b.extend([1-y]*(c//2) + [y]*(c//2+1))
r = max(r, (c+1)//2)

print(r)
print(*b)


import math

n=int(input())
a=list(map(int,input().split()))
segs=[]
st=-1
for i in range(n):
	iso=False if i==0 or i==n-1 else a[i-1]==a[i+1] and a[i]!=a[i-1]
	if iso and st==-1:
		st=i
	elif not iso and st!=-1:
		segs.append((st,i-1))
		st=-1
ans=0
for l,r in segs:
	span=r-l+1
	ans=max(ans,span)
	for i in range(span//2):
		a[l+i]=a[l-1]
		a[r-i]=a[r+1]
	if span%2:
		j=l+span//2
		a[j]=sorted([a[j-1],a[j],a[j+1]])[1]
print(math.ceil(ans/2))
print(*a)