一个名叫 Vasya 的男生喜欢阅读编程和数学方面的书籍。他最近读了一篇百科全书文章,描述了中值平滑(或中值滤波器)的方法及其在科学和工程中的许多应用。瓦夏非常喜欢这个方法的想法,他决定在实践中尝试一下。
将中值平滑的最简单变体应用于数字序列 a1, a2, ..., an 将产生通过以下算法获得的新序列 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 序列,确定它是否变得稳定。此外,如果它变得稳定,那么您应该确定它会是什么样子,以及需要对初始序列应用中值平滑算法多少次才能获得稳定的序列。
输入
输入的第一个输入行包含一个整数 n (3 ≤ n ≤ 500 000) - 初始序列的长度。
下一行包含 n 个整数 a1, a2, ..., an(ai = 0 或 ai = 1),给出初始序列本身。
输出
如果序列永远不会变得稳定,则打印一个数字 - 1。
否则,首先打印一个整数 - 在初始序列变得稳定之前需要将中值平滑算法应用于初始序列的最小次数。在第二行中打印 n 个由空格分隔的数字 - 结果序列本身。
示例
输入 #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
注意
在第二个样本中,稳定分两步进行:$$01010 \rightarrow 00100 \rightarrow 00000$$,并且序列 00000 显然是稳定的。