次に、次の問題を解決するためのアルゴリズムを作成してほしいです。

リサは、Integersシーケンスで遊ぶのが大好きです。整数の新しいシーケンス** ai ** long ** n **を受け取ると、すべての単調なサブセクションを探し始めます。単調な代替物*[l、r]*は、2つのインデックス** l **および** r ***（1≤l<r≤n）で定義されます。 ..、r -1：ai≤ai+1*または∀i=* l、l+1、…、r -1：ai≥ai+1*。

リサは、単調な物質*[l、r]*が退屈なしきい値** k **を持つ単調な物質*[l、r]*がある場合、シーケンス** ai **は退屈であると考えています。つまり、*r -l+1 = k*。

ルーカスには、彼がリサに紹介したいシーケンス** bi **がありますが、リサにとってシーケンスは退屈かもしれません。そのため、彼はシーケンスのいくつかの要素を変更したいと考えています** bi **リサが彼女と遊ぶことで退屈しないようにします。しかし、ルーカスは怠zyであり、シーケンスの要素の最小数を変更したい** bi **。あなたの仕事は、ルーカスが必要な変更を見つけるのを助けることです。

**入り口**

最初の入り口には、2つの整数が含まれています** n **および** k ***（3≤k≤n≤106）* - リサのシーケンスの長さと退屈なしきい値。2番目の行には** n **整数** bi ***（1≤bi≤99999）* - ルーカスが持っている元のシーケンスが含まれています。

**出口**

最初の行では、整数** m **を印刷します -  ** bi **の要素の最小数は、リサにとって退屈でないシーケンスを変更する必要があります。2行目では、** n ** integers ** ai ***（0≤ai≤100000）*を印刷します。 ** bi **正確に** m **位置。

必要なプログラミング言語でアルゴリズムを作成します;）。
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 ;).