Lisa’s Sequences
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 ≤ l < r ≤ n) such that ∀i = l, l + 1, ..., r - 1: a[i] ≥ a[i+1] or ∀i = l, l + 1, ..., r - 1: a[i] ≥ 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.
Input
The first line contains two integers n and k (3 ≤ k ≤ n ≤ 10^6) - the length of the sequence and Lisa’s boredom threshold. The second line contains n integers b[i] (1 ≤ b[i] ≤ 99999) - the original sequence that Lucas has.
Output
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 ≤ a[i] ≤ 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 m positions.