| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 (추가 시간 없음) | 1024 MB | 0 | 0 | 0 | 0.000% |
Lisa loves playing with the sequences of integers. When she gets a new integer sequence $a_i$ of length $n,ドル she starts looking for all monotone subsequences. A monotone subsequence $[l, r]$ is defined by two indices $l$ and $r$ (1ドル \le l < r \le n$) such that $\forall i = l, l+1, \ldots, r-1: a_i \le a_{i+1}$ or $\forall i = l, l+1, \ldots, r-1: a_i \ge a_{i+1}$.
Lisa considers a sequence $a_i$ to be boring if there is a monotone subsequence $[l, r]$ that is as long as her boredom threshold $k,ドル that is when $r - l + 1 = k$.
Lucas has a sequence $b_i$ that he wants to present to Lisa, but the sequence might be boring for Lisa. So, he wants to change some elements of his sequence $b_i,ドル so that Lisa does not get bored playing with it. However, Lucas is lazy and wants to change as few elements of the sequence $b_i$ as possible. Your task is to help Lucas find the required changes.
The first line of the input contains two integers $n$ and $k$ (3ドル \le k \le n \le 10^6$) --- the length of the sequence and Lisa's boredom threshold. The second line contains $n$ integers $b_i$ (1ドル \le b_i \le 99,999円$) --- the original sequence that Lucas has.
On the first line output an integer $m$ --- the minimal number of elements in $b_i$ that needs to be changed to make the sequence not boring for Lisa. On the second line output $n$ integers $a_i$ (0ドル \le a_i \le 100,000円$), so that the sequence of integers $a_i$ is not boring for Lisa and is different from the original sequence $b_i$ in exactly $m$ positions.
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