Лиза любит играть с последовательностями целых чисел. Получив новую целочисленную последовательность 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 позиций.