CF1322E Median Mountain Range

Berland 是一个地理多样性极高的大国。其中最著名的自然景观之一是“中值山脉”。这条山脉由 $n$ 个山峰组成，所有山峰都位于同一直线上，依次编号为 $1$ 到 $n$。第 $i$ 个山峰的高度为 $a_i$。 “中值山脉”以每天都会发生的山峰对齐现象而闻名。在对齐的时刻，从第 $2$ 座到第 $n-1$ 座的每一座山峰的高度都会同时变为它与相邻两座山峰的高度的中值。形式化地说，若对齐前各山峰的高度为 $b_i$，则对齐后新的高度 $a_i$ 如下：$a_1 = b_1$，$a_n = b_n$，对于所有 $i$ 满足 $2 \le i \le 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$ —— 至少有一座山峰高度发生变化的对齐次数。同时，政府还需要知道经过 $c$ 次对齐后山峰的最终高度，即这些高度将永远保持不变。请帮助科学家们解决这个重要问题！

第一行包含一个整数 $n$（$1 \le n \le 500\,000$），表示山峰的数量。 第二行包含 $n$ 个整数 $a_1, a_2, a_3, \ldots, a_n$（$1 \le a_i \le 10^9$），表示当前每座山峰的高度。

第一行输出一个整数 $c$，表示至少有一座山峰高度发生变化的对齐次数。 第二行输出 $n$ 个整数，表示经过 $c$ 次对齐后每座山峰的最终高度。

在第一个样例中，编号为 $1$ 和 $5$ 的山峰高度始终不变。由于 $1, 2, 1$ 的中值为 $1$，第二和第四座山峰在第一次对齐后高度变为 $1$；而 $2, 1, 2$ 的中值为 $2$，第三座山峰在第一次对齐后高度变为 $2$。因此，第一次对齐后高度为 $1, 1, 2, 1, 1$。第二次对齐后，高度变为 $1, 1, 1, 1, 1$，之后高度不再变化，所以总共有 $2$ 次对齐导致山峰高度发生变化。 在第三个样例中，对齐不会改变任何山峰的高度，因此有 $0$ 次对齐导致高度变化。 由 ChatGPT 4.1 翻译