CF590A.Median Smoothing

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.

一名名叫瓦夏的中学生热爱阅读编程与数学方面的书籍。他最近读到了一篇百科全书文章，其中介绍了中值平滑（又称中值滤波）方法及其在科学与工程中的诸多应用。瓦夏非常喜爱该方法的思想，于是决定在实践中尝试一下。

对数字序列 $a_1,\,a_2,\,\dots,\,a_n$ 应用最简单的中值平滑变体会得到一个新序列 $b_1,\,b_2,\,\dots,\,b_n$，其构造算法如下：

• $b_1 = a_1$，$b_n = a_n$，即新序列的首项与末项分别与原序列对应位置的数相同；
• 对于 $i = 2,\,\dots,\,n-1$，值 $b_i$ 等于三个数 $a_{i-1},\,a_i,\,a_{i+1}$ 的中位数。

三个数的中位数，是指将这三个数按非递减顺序排列后位于第二位的那个数。例如，集合 $\{5,\,1,\,2\}$ 的中位数是 $2$；集合 $\{1,\,0,\,1\}$ 的中位数是 $1$。

为了简化任务，瓦夏决定仅对由 0 和 1 组成的序列 应用该方法。

完成一次该操作后，瓦夏观察所得序列并思考：如果我再对它应用一次该算法，接着对新结果再应用一次，如此反复下去呢？瓦夏尝试了几个例子，发现经过若干次中值平滑操作后，序列可能最终停止变化。我们称一个序列是稳定的，当且仅当对其应用一次中值平滑操作后，序列保持不变。

现在瓦夏想知道：任意给定的 0-1 序列是否总会在有限步后变为稳定序列？他请你编写一个程序：对于给定的一个由 0 和 1 构成的序列，判断它是否最终会变为稳定序列；若会，则进一步求出其最终的稳定形态，以及从初始序列出发、需应用多少次中值平滑操作才能首次得到该稳定序列。

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.

输入的第一行包含一个整数 $n$（$3 \leq n \leq 500\,000$）—— 表示初始序列的长度。

下一行包含 $n$ 个整数 $a_1,\,a_2,\,...,\,a_n$（其中每个 $a_i = 0$ 或 $a_i = 1$），表示初始序列本身。

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$。

否则，首先输出一个整数——即对初始序列应用中位数平滑算法使其变为稳定状态所需的最少次数。在第二行输出 $n$ 个用空格分隔的数字——即最终得到的序列本身。

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

在第二个样例中，稳定化过程分为两个步骤：，而序列 00000 显然是稳定的。