Ahora me gustaría que crearas un algoritmo para resolver el siguiente problema:

A Lisa le encanta jugar con las secuencias de enteros. Cuando recibe una nueva secuencia de enteros **ai** de longitud **n**, empieza a buscar todas las subsecuencias monótonas. Una subsecuencia monótona *[l,r]* se define por dos índices **l** y **r** *(1≤l<r≤n)* tal que ∀i = *l,l+1,…,r−1:ai≤ai+1* o ∀i = *l,l+1,…,r−1:ai≥ai+1* .

Lisa considera que una secuencia **ai** es aburrida si hay una subsecuencia monótona *[l,r]* que tiene la misma longitud que su umbral de aburrimiento **k** , es decir, cuando *r−l+1=k* .

Lucas tiene una secuencia **bi** que quiere presentarle a Lisa, pero la secuencia puede ser aburrida para Lisa. Así que quiere cambiar algunos elementos de su secuencia **bi** para que Lisa no se aburra jugando con ella. Sin embargo, Lucas es perezoso y quiere cambiar el menor número posible de elementos de la secuencia **bi** . Tu tarea es ayudar a Lucas a encontrar los cambios necesarios.

**Entrada** 

La primera línea de la entrada contiene dos enteros **n** y **k** *(3≤k≤n≤106 )* — la longitud de la secuencia y el umbral de aburrimiento de Lisa. La segunda línea contiene **n** enteros **bi** *(1≤bi≤99999 )* — la secuencia original que tiene Lucas.

**Salida**

En la primera línea imprime un entero **m** — el número mínimo de elementos en **bi** que hay que cambiar para hacer que la secuencia no sea aburrida para Lisa. En la segunda línea imprime **n** enteros **ai** *(0≤ai≤100000)*, de modo que la secuencia de enteros **ai** no sea aburrida para Lisa y sea diferente de la secuencia original **bi** en exactamente **m** posiciones.

Crea el algoritmo en el lenguaje de programación que quieras ;).
spam lang_mismatch pii not_appropriate hate_speech sexual_content quality toxicity humor creativity violence