L. Lisa's Sequences
dp
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.