P12801 [NERC 2022] Lisa's Sequences

丽莎喜欢玩整数序列。当她得到一个长度为 $n$ 的新整数序列 $a_i$ 时，她会开始寻找所有 **单调** 子序列。一个单调子序列 $[l, r]$ 由两个索引 $l$ 和 $r$ ($1 \le l < r \le n$) 定义，满足 $\forall i = l, l+1, \ldots, r-1: a_i \le a_{i+1}$ 或 $\forall i = l, l+1, \ldots, r-1: a_i \ge a_{i+1}$。 如果存在一个长度等于她的厌倦阈值 $k$ 的单调子序列 $[l, r]$，即 $r - l + 1 = k$，丽莎就认为序列 $a_i$ 是 **无聊的**。 卢卡斯有一个序列 $b_i$ 想送给丽莎，但这个序列对丽莎来说可能很无聊。所以，他想修改序列 $b_i$ 中的一些元素，使得丽莎在玩这个序列时不会感到无聊。然而，卢卡斯很懒，只想修改序列 $b_i$ 中尽可能少的元素。你的任务是帮助卢卡斯找到需要进行的修改。

输入的第一行包含两个整数 $n$ 和 $k$ ($3 \le k \le n \le 10^6$)——序列的长度和丽莎的厌倦阈值。第二行包含 $n$ 个整数 $b_i$ ($1 \le b_i \le 99\,999$)——卢卡斯拥有的原始序列。

在第一行输出一个整数 $m$——为了使序列对丽莎来说不无聊，需要修改 $b_i$ 中元素的最少数量。在第二行输出 $n$ 个整数 $a_i$ ($0 \le a_i \le 100\,000$)，使得整数序列 $a_i$ 对丽莎来说不无聊，并且与原始序列 $b_i$ 恰好在 $m$ 个位置上不同。