Lisa's Sequences#11331
Lisa loves playing with the sequences of integers. When she gets a new integer sequence a_i of length , she starts looking for all monotone subsequences. A monotone subsequence [l, r] is defined by two indices and (1 \leq l < r \leq n) such that \forall i = l, l + 1, \ldots, r - 1: a_i \geq a_{i+1} or \forall i = l, l + 1, \ldots, r - 1: a_i \leq 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 , 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 contains two integers and (3 \leq k \leq n \leq 10^6) - the length of the sequence and Lisa's boredom threshold. The second line contains integers b_i (1 \leq b_i \leq 99999) - the original sequence that Lucas has.
On the first line output an integer - 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 integers a_i (0 \leq a_i \leq 10^5), so that the sequence of integers a_i is not boring for Lisa and is different from the original sequence b_i in exactly positions.
Example 1
Example 2
Example 3
Example 4
Example 5
Example 6
Example 7
Example 8
Example 9