← 返回题目列表

Codeforces · 1773/L

L. 丽莎的序列

中文机器翻译题面 查看原题

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