Lisa 喜欢玩整数序列。当她得到一个长度为 $$$n$$$ 的新整数序列 $$$a_i$$$ 时,她开始寻找所有 单调 子序列。单调子序列 $$$[l, r]$$$ 由两个索引 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \lt 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}$$$。
Lisa 认为序列 $$$a_i$$$ 是 无聊 如果存在一个单调子序列$$$[l, r]$$$,其长度与她的无聊阈值$$$k$$$一样长,即$$$r - l + 1 = k$$$。
卢卡斯有一个序列 $$$b_i$$$ 想要呈现给丽莎,但该序列对丽莎来说可能很无聊。因此,他想更改序列 $$$b_i$$$ 中的一些元素,这样 Lisa 就不会觉得无聊。然而,Lucas 很懒,想要更改序列 $$$b_i$$$ 中尽可能少的元素。您的任务是帮助卢卡斯找到所需的更改。
输入
输入的第一行包含两个整数 $$$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$$$ 对于 Lisa 来说并不无聊,并且在 $$$m$$$ 位置上与原始序列 $$$b_i$$$ 不同。
示例
输入复制
5 3 1 2 3 4 5
输出复制
2 1 0 3 0 5
输入复制
6 3 1 1 1 1 1 1
输出复制
3 1 100000 0 1 0 1
输入复制
6 4 1 1 4 4 1 1
输出复制
1 1 1 4 0 1 1
输入复制
6 4 4 4 4 2 2 2
输出复制
2 4 4 0 2 0 2
输入复制
6 4 4 4 4 3 4 4
输出复制
1 4 4 100000 3 4 4
输入复制
8 4 2 1 1 3 3 1 1 2
输出复制
2 2 1 1 3 0 1 0 2
输入复制
10 4 1 1 1 2 2 1 1 2 2 1
输出复制
2 1 1 100000 2 2 100000 1 2 2 1
输入复制
7 5 5 4 4 3 4 4 4
输出复制
0 5 4 4 3 4 4 4
输入复制
10 10 1 1 1 1 1 1 1 1 1 1
输出复制
1 1 1 1 1 1 1 1 1 0 1