贝尔兰 — 是一个地理多样化的大国。贝尔兰最著名的自然景点之一是“米底山脉”。该山脉由 $$$n$$$ 山峰组成,位于一条直线上,并按 $$$1$$$ 到 $$$n$$$ 的顺序编号。第 $$$i$$$ 个山顶的高度为 $$$a_i$$$。
“中位山脉”因每天发生的所谓山峰排列而闻名。在从 $$$2$$$ 到 $$$n - 1$$$ 的每座山同时对齐的时刻,其高度变得等于它和两座相邻山之间的中位高度。形式上,如果在对齐之前高度相等 $$$b_i$$$,则在对齐之后新高度 $$$a_i$$$ 如下: $$$a_1 = b_1$$$、$$$a_n = b_n$$$ 以及对于从 $$$2$$$ 到 $$$n - 1$$$ $$$a_i = 的所有 $$$i$$$ \texttt{中值}(b_{i-1}, b_i, b_{i+1})$$$。三个整数的中位数是其中第二大的数。例如,$$$\texttt{中位数}(5,1,2) = 2$$$,$$$\texttt{中位数}(4,2,4) = 4$$$。
最近,Berland科学家证明,无论山脉目前的高度是多少,对齐过程迟早都会稳定下来,即在某个时刻,对齐后山脉的高度将不再改变。 Berland 政府希望了解这种情况多久会发生,即找出 $$$c$$$ 的值 — 将会发生多少次对齐,这将改变至少一座山的高度。此外,Berland 政府需要在 $$$c$$$ 对齐后确定山脉的高度,即找出山脉永远保持的高度。帮助科学家解决这个重要问题!
输入
第一行包含整数 $$$n$$$ ($$$1 \le n \le 500\,000$$$) — 山脉的数量。
第二行包含整数 $$$a_1, a_2, a_3, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 山脉的当前高度。
输出
在第一行中打印 $$$c$$$ — 对齐数量,这会改变至少一座山的高度。
在第二行中打印 $$$n$$$ 整数 - $$$c$$$ 对齐后山脉的最终高度。
示例
输入 #1
5 1 2 1 2 1
输出 #1
2 1 1 1 1 1
输入 #2
6 1 3 2 5 4 6
输出 #2
1 1 2 3 4 5 6
输入 #3
6 1 1 2 2 1 1
输出 #3
0 1 1 2 2 1 1
注意
在第一个示例中,索引 $$$1$$$ 和 $$$5$$$ 处的山脉高度永远不会改变。由于 $$$1$$$、$$$2$$$、$$$1$$$ 的中位数为 $$$1$$$,因此第一次对齐后第二个和第四个山的高度将为 1,并且由于 $$$2$$$、$$$1$$$、$$$2$$$ 的中位数为 $$$2$$$,因此第一次对齐后第三个山的高度为 2。这样,一次对齐后,高度为 $$$1$$$、$$$1$$$、$$$2$$$、$$$1$$$、$$$1$$$。在第二次对齐之后,高度变为 $$$1$$$、$$$1$$$、$$$1$$$、$$$1$$$、$$$1$$$ 并且从现在开始永远不会改变,因此只有 $$$2$$$ 对齐会改变山的高度。
在第三个示例中,路线不会改变任何山的高度,因此改变任何高度的路线数量为$$$0$$$。