CF1322E.Median Mountain Range

Berland — is a huge country with diverse geography. One of the most famous natural attractions of Berland is the "Median mountain range". This mountain range is $n$ mountain peaks, located on one straight line and numbered in order of $1$ to $n$. The height of the $i$-th mountain top is $a_i$.

"Median mountain range" is famous for the so called alignment of mountain peaks happening to it every day. At the moment of alignment simultaneously for each mountain from $2$ to $n - 1$ its height becomes equal to the median height among it and two neighboring mountains. Formally, if before the alignment the heights were equal $b_i$, then after the alignment new heights $a_i$ are as follows: $a_1 = b_1$, $a_n = b_n$ and for all $i$ from $2$ to $n - 1$ $a_i = \texttt{median}(b_{i-1}, b_i, b_{i+1})$. The median of three integers is the second largest number among them. For example, $\texttt{median}(5,1,2) = 2$, and $\texttt{median}(4,2,4) = 4$.

Recently, Berland scientists have proved that whatever are the current heights of the mountains, the alignment process will stabilize sooner or later, i.e. at some point the altitude of the mountains won't changing after the alignment any more. The government of Berland wants to understand how soon it will happen, i.e. to find the value of $c$ — how many alignments will occur, which will change the height of at least one mountain. Also, the government of Berland needs to determine the heights of the mountains after $c$ alignments, that is, find out what heights of the mountains stay forever. Help scientists solve this important problem!

Berland 是一个幅员辽阔、地理环境多样的国家。Berland 最著名的自然景观之一是“中位数山脉”。该山脉由 $n$ 座山峰组成，它们位于同一条直线上，并按顺序编号为 $1$ 至 $n$。第 $i$ 座山峰的高度为 $a_i$。

“中位数山脉”因每天发生的所谓“山峰对齐”现象而闻名。在对齐时刻，对于从第 $2$ 座到第 $n-1$ 座的每一座山峰，其高度会同时变为它自身及其两个相邻山峰高度的中位数。形式化地，若对齐前各山峰高度为 $b_i$，则对齐后的新高度 $a_i$ 定义如下：$a_1 = b_1$，$a_n = b_n$，且对所有 $i$ 从 $2$ 到 $n-1$，有 $a_i = \texttt{median}(b_{i-1}, b_i, b_{i+1})$。三个整数的中位数是其中第二大的数。例如，$\texttt{median}(5,1,2) = 2$，而 $\texttt{median}(4,2,4) = 4$。

最近，Berland 的科学家已证明：无论当前各山峰高度如何，该对齐过程迟早会稳定下来，即在某一时刻之后，山峰高度在每次对齐操作后将不再发生变化。Berland 政府希望了解这一稳定状态何时到来，即求出 $c$ —— 使得至少一座山峰高度发生改变的对齐操作次数。此外，Berland 政府还需确定经过 $c$ 次对齐操作后的山峰高度，即最终永久保持不变的山峰高度。请帮助科学家解决这一重要问题！

The first line contains integers $n$ ($1 \le n \le 500\,000$) — the number of mountains.

The second line contains integers $a_1, a_2, a_3, \ldots, a_n$ ($1 \le a_i \le 10^9$) — current heights of the mountains.

第一行包含一个整数 $n$（$1 \le n \le 500\,000$）—— 山峰的数量。

第二行包含 $n$ 个整数 $a_1, a_2, a_3, \ldots, a_n$（$1 \le a_i \le 10^9$）—— 各山峰当前的高度。

In the first line print $c$ — the number of alignments, which change the height of at least one mountain.

In the second line print $n$ integers — the final heights of the mountains after $c$ alignments.

第一行输出 $c$ —— 使至少一座山的高度发生变化的调整次数。

第二行输出 $n$ 个整数 —— 经过 $c$ 次调整后各座山的最终高度。

In the first example, the heights of the mountains at index $1$ and $5$ never change. Since the median of $1$, $2$, $1$ is $1$, the second and the fourth mountains will have height 1 after the first alignment, and since the median of $2$, $1$, $2$ is $2$, the third mountain will have height 2 after the first alignment. This way, after one alignment the heights are $1$, $1$, $2$, $1$, $1$. After the second alignment the heights change into $1$, $1$, $1$, $1$, $1$ and never change from now on, so there are only $2$ alignments changing the mountain heights.

In the third examples the alignment doesn't change any mountain height, so the number of alignments changing any height is $0$.

在第一个例子中，索引为 $1$ 和 $5$ 处的山峰高度始终不变。由于 $1$、$2$、$1$ 的中位数为 $1$，因此第一次对齐后，第二座和第四座山峰的高度变为 $1$；又因 $2$、$1$、$2$ 的中位数为 $2$，所以第一次对齐后，第三座山峰的高度变为 $2$。如此一来，第一次对齐后的山峰高度序列为 $1$、$1$、$2$、$1$、$1$。第二次对齐后，高度序列变为 $1$、$1$、$1$、$1$、$1$，此后不再发生变化，因此仅有 $2$ 次对齐改变了山峰高度。

在第三个例子中，对齐操作未改变任何山峰的高度，因此改变山峰高度的对齐次数为 $0$。