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$ 个位置上不同。

输入输出样例 #1

输入 #1

5 3
1 2 3 4 5

输出 #1

2
1 0 3 0 5

输入输出样例 #2

输入 #2

6 3
1 1 1 1 1 1

输出 #2

3
1 100000 0 1 0 1

输入输出样例 #3

输入 #3

6 4
1 1 4 4 1 1

输出 #3

1
1 1 4 0 1 1

输入输出样例 #4

输入 #4

6 4
4 4 4 2 2 2

输出 #4

2
4 4 0 2 0 2

输入输出样例 #5

输入 #5

6 4
4 4 4 3 4 4

输出 #5

1
4 4 100000 3 4 4

输入输出样例 #6

输入 #6

8 4
2 1 1 3 3 1 1 2

输出 #6

2
2 1 1 3 0 1 0 2

输入输出样例 #7

输入 #7

10 4
1 1 1 2 2 1 1 2 2 1

输出 #7

2
1 1 100000 2 2 100000 1 2 2 1

输入输出样例 #8

输入 #8

7 5
5 4 4 3 4 4 4

输出 #8

0
5 4 4 3 4 4 4

输入输出样例 #9

输入 #9

10 10
1 1 1 1 1 1 1 1 1 1

输出 #9

1
1 1 1 1 1 1 1 1 0 1