Послідовність Лізи#11331
Ліза любить грати з послідовностями цілих чисел. Коли вона отримує нову цілочисельну послідовність a_i довжини , вона починає шукати всі монотонні підпослідовності. Монотонна підпослідовність [l, r] визначається двома індексами і (1 \leq l < r \leq n) такими, що для всіх i = l, l + 1, \ldots, r - 1 виконується a_i \geq a_{i+1} або a_i \leq a_{i+1}.
Ліза вважає послідовність a_i нудною, якщо існує монотонна підпослідовність [l, r], довжина якої дорівнює її порогу нудьги , тобто коли r - l + 1 = k.
У Лукаса є послідовність b_i, яку він хоче показати Лізі, але ця послідовність може здатися їй нудною. Тому він хоче змінити деякі елементи своєї послідовності b_i, щоб Лізі не набридло грати з нею. Проте Лукас ледачий і прагне змінити якомога менше елементів послідовності b_i. Ваше завдання — допомогти Лукасу знайти необхідні зміни.
У першому рядку записані два цілі числа і (3 \leq k \leq n \leq 10^6) — довжина послідовності та поріг нудьги Лізи. У другому рядку міститься цілих чисел b_i (1 \leq b_i \leq 99999) — початкова послідовність, яку має Лукас.
У першому рядку виведіть ціле число — мінімальну кількість елементів у b_i, які потрібно змінити, щоб послідовність не була нудною для Лізи. У другому рядку виведіть цілих чисел a_i (0 \leq a_i \leq 10^5), так що послідовність цілих чисел a_i не нудна для Лізи і відрізняється від початкової послідовності b_i рівно на позицій.
Приклад 1
Приклад 2
Приклад 3
Приклад 4
Приклад 5
Приклад 6
Приклад 7
Приклад 8
Приклад 9