CF1773L Lisa's Sequences

Lisa 喜欢玩整数序列。当她得到一个长度为 $n$ 的新整数序列 $a_i$ 时，她会开始寻找所有的单调子序列。一个单调子序列 $[l, r]$ 由两个下标 $l$ 和 $r$（$1 \le l < r \le n$）定义，满足以下两种情况之一： - 对于所有 $i = l, l+1, \ldots, r-1$，都有 $a_i \le a_{i+1}$； - 对于所有 $i = l, l+1, \ldots, r-1$，都有 $a_i \ge a_{i+1}$。 如果存在一个长度恰好等于她的无聊阈值 $k$ 的单调子序列 $[l, r]$，即 $r - l + 1 = k$，Lisa 就会觉得序列 $a_i$ 很无聊。 Lucas 有一个序列 $b_i$，他想把它展示给 Lisa，但这个序列可能会让 Lisa 感到无聊。因此，他想修改序列 $b_i$ 的一些元素，使得 Lisa 不会觉得无聊。然而，Lucas 很懒，他希望修改 $b_i$ 的元素数量尽可能少。你的任务是帮助 Lucas 找到需要修改的最少元素数目。

第一行包含两个整数 $n$ 和 $k$（$3 \le k \le n \le 10^6$），分别表示序列的长度和 Lisa 的无聊阈值。第二行包含 $n$ 个整数 $b_i$（$1 \le b_i \le 99\,999$），表示 Lucas 原有的序列。

第一行输出一个整数 $m$，表示需要修改 $b_i$ 的最小元素数量，使得序列对 Lisa 来说不再无聊。第二行输出 $n$ 个整数 $a_i$（$0 \le a_i \le 100\,000$），表示修改后的序列，且 $a_i$ 与原序列 $b_i$ 恰好有 $m$ 个位置不同，并且对 Lisa 来说不无聊。

由 ChatGPT 4.1 翻译