Послідовність Лізи
Ліза любить грати з послідовностями цілих чисел. Коли вона отримує нову цілочисельну послідовність a[i] довжини n, вона починає шукати всі монотонні підпослідовності. Монотонна підпослідовність [l, r] визначається двома індексами l і r (1 ≤ l < r ≤ n) такими, що для всіх i = l, l + 1, ..., r - 1 виконується a[i] ≥ a[i+1] або a[i] ≤ a[i+1].
Ліза вважає послідовність a[i] нудною, якщо існує монотонна підпослідовність [l, r], довжина якої дорівнює її порогу нудьги k, тобто коли r - l + 1 = k.
У Лукаса є послідовність b[i], яку він хоче показати Лізі, але ця послідовність може здатися їй нудною. Тому він хоче змінити деякі елементи своєї послідовності b[i], щоб Лізі не набридло грати з нею. Проте Лукас ледачий і прагне змінити якомога менше елементів послідовності b[i]. Ваше завдання — допомогти Лукасу знайти необхідні зміни.
Вхідні дані
У першому рядку записані два цілі числа n і k (3 ≤ k ≤ n ≤ 10^6) — довжина послідовності та поріг нудьги Лізи. У другому рядку міститься n цілих чисел b[i] (1 ≤ b[i] ≤ 99999) — початкова послідовність, яку має Лукас.
Вихідні дані
У першому рядку виведіть ціле число m — мінімальну кількість елементів у b[i], які потрібно змінити, щоб послідовність не була нудною для Лізи. У другому рядку виведіть n цілих чисел a[i] (0 ≤ a[i] ≤ 10^5), так що послідовність цілих чисел a[i] не нудна для Лізи і відрізняється від початкової послідовності b[i] рівно на m позицій.