Median Smoothing

题意翻译

# 题目描述 最简单的中值滤波是对一个序列 $a_1,a_2,…,a_n$ ，转换为一个新的序列 $b_1,b_2,…,b_n$ ，规则如下： - $b_1=a_1,b_n=a_n$ ，即第一个和最后一个元素不变。 - $b_i(1<i<n)$ 为 $a_{i-1},a_i,a_{i+1}$ 的中位数。 求对于一个 01 序列 $a$ ，它经过几次操作会变成“稳定的”，或者永远稳定不了。 ## 输入格式 第一行一个整数 $n$ ，表示序列的长度。 接下来一行 $n$ 个整数 $a_1,a_2,…,a_n$ ，表示原序列。 ## 输出格式 假如该序列永远也不会稳定，则输出 $-1$ 。 否则输出，一行一个整数，表示需要多少次操作原序列才会稳定，并在下一行输出最终稳定的序列。 ## 说明 ### 样例解释 经过两次操作：$01010\longrightarrow00100\longrightarrow00000$ ，$00000$ 显然是稳定的序列。

题目描述

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.

输入输出格式

输入格式

The first input line of the input contains a single integer $ n $ ( $ 3<=n<=500000 $ ) — 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.

输出格式

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.

输入输出样例

输入样例 #1

4
0 0 1 1

输出样例 #1

0
0 0 1 1

输入样例 #2

5
0 1 0 1 0

输出样例 #2

2
0 0 0 0 0

说明

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