Лиза любит играть с последовательностями целых чисел. Получив новую целочисленную последовательность a[i]
длины n, она начинает искать все монотонные подпоследовательности. Монотонная подпоследовательность [l, r] определяется двумя индексами l и r (1 ≤ l < r ≤ n) такими, что ∀i = l, l + 1, ..., r - 1: a[i]
≥ a[i+1]
или ∀i = l, l + 1, ..., r - 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 позиций.