[AdditionalFile5401.zip](file://AdditionalFile5401.zip?type=additional_file)

#5401. 「OOI 2020 Day 1」中位山脉

标签: 传统 | 时间限制: 2000 ms | 内存限制: 512 MiB |

题目描述

题目译自 Open Olympiad in Informatics 2020 Day1 T1 「Медианный горный хребет / Median mountain range」。

伯兰迪亚是一个地理环境多样的巨大国家。其最著名的自然景观之一是「中位山脉」。这座山脉由 $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 = \operatorname{median}(b_{i-1}, b_i, b_{i+1})$。三个数的中位数是指将这三个数按升序排列后位于中间的那个数。例如，$\operatorname{median}(5,1,2) = 2$，$\operatorname{median}(4,2,4) = 4$。

最近，伯兰迪亚的科学家们证明，无论山峰的初始高度如何，平整过程最终都会稳定下来，即在某一时刻，山峰高度在平整后将不再发生变化。伯兰迪亚政府希望了解这一过程需要多少年才能稳定，也就是找到 $c$ 的值——表示有多少次平整过程中至少有一个山峰的高度发生了变化。请帮助科学家解决这一重要问题！

请注意，在某些子任务中，除了需要计算 $c$ 的值外，还需要确定经过 $c$ 次平整后的山峰高度，即了解山峰最终稳定的高度。

输入格式

第一行包含两个整数 $n$ 和 $t$ $(1 \leq n \leq 500000, 0 \leq t \leq 1)$，分别表示山峰数量和一个参数，用于确定是否需要输出最终的山峰高度。

第二行包含 $n$ 个整数 $a_1, a_2, a_3, \ldots, a_n$ $(1 \leq a_i \leq 10^{9})$，表示山峰当前的高度。

输出格式

第一行输出 $c$，即山峰高度发生变化的平整次数。

如果 $t = 1$，则在第二行输出 $n$ 个数字，表示经过 $c$ 次平整后的最终山峰高度。

样例 1

输入

5 1
1 2 1 2 1

输出

2
1 1 1 1 1

在第一个样例中，第 $1$ 个和第 $5$ 个位置的山峰高度不变。由于数字 $1,2, 1$ 的中位数为 $1$，因此在第一次平整后，第 $2$ 和第 $4$ 个位置的山峰高度变为 $1$；而数字 $2, 1, 2$ 的中位数为 $2$，因此第 $3$ 个位置的山峰高度在第一次平整后变为 $2$。第一次平整后，山峰高度为 $1, 1, 2, 1, 1$。第二次平整后，高度变为 $1, 1, 1, 1, 1$，此后不再变化，因此总共有 $2$ 次改变了高度的平整。

样例 2

输入

6 1
1 3 2 5 4 6

输出

1
1 2 3 4 5 6

样例 3

输入

6 0
1 1 2 2 1 1

输出

0

在第三个样例中，平整后没有一个山峰的高度发生变化，因此改变了高度的平整次数为 $0$。由于 $t = 0$，无需输出最终的山峰高度。

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。