Последовательность Лизы
Последовательность Лизы
Лиза любит играть с последовательностями целых чисел. Получив новую целочисленную последовательность ai
длины n, она начинает искать все монотонные подпоследовательности. Монотонная подпоследовательность [l, r] определяется двумя индексами l и r (1 ≤ l < r ≤ n) такими, что ∀i = l, l + 1, ..., r - 1: ai
≥ ai+1
или ∀i = l, l + 1, ..., r - 1: ai
≥ ai+1
.
Лиза считает последовательность ai
скучной, если существует монотонная подпоследовательность [l, r], длина которой равна ее порогу скуки k, то есть когда r - l + 1 = k.
У Лукаса есть последовательность bi
, которую он хочет показать Лизе, но эта последовательность может показаться Лизе скучной. Итак, он хочет изменить некоторые элементы своей последовательности bi
, чтобы Лизе не надоело играть с ней. Однако Лукас ленив и хочет изменить как можно меньше элементов последовательности bi
. Ваша задача - помочь Лукасу найти необходимые изменения.
Входные данные
В первой строке записаны два целых числа n и k (3 ≤ k ≤ n ≤ 106
) - длина последовательности и число Лизы - порог скуки. Вторая строка содержит n целых чисел bi
(1 ≤ bi
≤ 99999) — исходная последовательность, которую имеет Лукас.
Выходные данные
В первой строке выведите целое число m - минимальное количество элементов в bi
, которое нужно изменить чтобы последовательность не была скучной для Лизы. Во второй строке выведите n целых чисел ai
(0 ≤ ai
≤ 105
), так что последовательность целых чисел ai
не скучна для Лизы и отличается от исходной последовательности bi
ровно на m позиций.
5 3 1 2 3 4 5
2 1 0 3 0 5
6 3 1 1 1 1 1 1
3 1 100000 0 1 0 1
6 4 1 1 4 4 1 1
1 1 1 4 0 1 1
6 4 4 4 4 2 2 2
2 4 4 0 2 0 2
6 4 4 4 4 3 4 4
1 4 4 100000 3 4 4
8 4 2 1 1 3 3 1 1 2
2 2 1 1 3 0 1 0 2
10 4 1 1 1 2 2 1 1 2 2 1
2 1 1 100000 2 2 100000 1 2 2 1
7 5 5 4 4 3 4 4 4
0 5 4 4 3 4 4 4
10 10 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0 1