ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

5049: 中值平滑

内存限制：256 MB 时间限制：2 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：5 通过：4
提交提交记录统计Web Board

题目描述

    一个名叫Vasya的小学生喜欢读编程和数学方面的书。他最近阅读了一篇百科全书文章，描述了中值平滑（或中值滤波器）的方法及其在科学和工程中的许多应用。Vasya非常喜欢这种方法的想法，他决定在实践中尝试一下。

将中值平滑的最简单变体应用于数字序列a1，a2，…，将产生新的序列b1、b2、，…，bn，通过以下算法获得：

        b1＝a1，bn＝an，即，新序列的第一个和最后一个编号与原始序列的对应编号匹配。

        对于i=2，…，n-1值bi等于三个值ai-1、ai和ai+1的中值。

    一组三个数字的中位数是排名第二的数字，当这三个数字以非递减顺序书写时。例如，集合5，1，2的中值是数字2，集合1，0，1的中值等于1。

    为了使任务更容易，Vasya决定将该方法应用于仅由0和1组成的序列。

    完成了一次程序后，Vasya查看了生成的序列并思考：如果我再次将算法应用于它，然后将其应用于下一个结果，如此类推Vasya尝试了几个例子，发现在应用了一些中值平滑算法之后，序列可以停止变化。我们说序列是稳定的，如果它在应用中值平滑时不发生变化。

    现在Vasya想知道，这个序列是否最终会变得稳定。他让你写一个程序，在给定一系列0和1的情况下，它将决定它是否稳定。此外，如果它变得稳定，那么您应该确定它看起来是什么样子，以及需要对初始序列应用中值平滑算法多少次才能获得稳定的序列。



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 a1,a2,...,an will result a new sequence b1,b2,...,bn obtained by the following algorithm:
  • b1=a1, bn=an, 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 bi is equal to the median of three values ai-1, ai and ai+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≤500000)− the length of the initial sequence.
The next line contains n integers a1,a2,...,an (ai=0 or ai=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, and the sequence 00000 is obviously stable.

输入格式

输入的第一行包含单个整数 n （3≤n≤500000）− 初始序列的长度。
下一行包含 n 个整数一个1，a2,...,an (一个i=0或一个i=1），给出初始序列本身。

输出格式

如果序列永远不会稳定，请打印一个数字-1。

否则，首先打印一个整数，即在初始序列稳定之前，对其应用中值平滑算法所需的最小次数。在第二行中，打印n个数字，用空格分隔，即生成的序列本身。

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
注意
在第二个样本中，稳定分两步进行，序列 00000 明显稳定。

输入样例 复制 

4
0 0 1 1

输出样例 复制 

0
0 0 1 1

分类标签