Liza'nın ardıcıllığı

Lisa tam ədədlərdən ibarət ardıcıllıqlarla oynamağı çox sevir. O, n uzunluqlu yeni tam ədədlər ardıcıllığı $a[i]$ aldıqda, bütün monoton altardıcıllıqları axtarmağa başlayır. Monoton altardıcıllıq [l, r] müəyyən edilir, burada iki indeks $l$ və $r$ (1 \leq l < r \leq n) elədir ki, bütün i = l, l + 1, ..., r - 1 üçün ya a[i] \geq a[i+1], ya da a[i] \leq a[i+1] şərti ödənir.

Lisa ardıcıllığı $a[i]$-ni darıxdırıcı hesab edir, əgər uzunluğu onun darıxma həddi $k$-yə bərabər olan bir monoton altardıcıllıq [l, r] varsa, yəni r - l + 1 = k olduqda.

Lucas Lisa-ya $b[i]$ ardıcıllığını təqdim etmək istəyir, amma bu ardıcıllıq onun üçün darıxdırıcı ola bilər. Buna görə də Lucas öz ardıcıllığı $b[i]$-də bəzi elementləri dəyişmək istəyir ki, Lisa ondan oynayarkən darıxmasın. Lakin Lucas tənbəldir və $b[i]$ ardıcıllığında mümkün qədər az elementi dəyişmək istəyir. Sizin vəzifəniz Lucas-a tələb olunan dəyişiklikləri tapmaqda kömək etməkdir.

Giriş Veriləri

Birinci sətirdə iki tam ədəd $n$ və $k$ (3 \leq k \leq n \leq 10^6) - ardıcıllığın uzunluğu və Lisa'nın darıxma həddi olan ədəd verilir. İkinci sətirdə $n$ tam ədəd $b[i]$ (1 \leq b[i] \leq 99999) - Lucasın malik olduğu ilkin ardıcıllıq verilir.

Çıxış Veriləri

Birinci sətirdə $m$ tam ədədini - $b[i]$ ardıcıllığında dəyişdirilməsi lazım olan minimum element sayını yazın ki, ardıcıllıq Lisa üçün darıxdırıcı olmasın. İkinci sətirdə $n$ tam ədəd $a[i]$ (0 \leq a[i] \leq 10^5) yazın ki, $a[i]$ tam ədədlər ardıcıllığı Lisa üçün darıxdırıcı olmasın və ilkin ardıcıllıq $b[i]$ ilə məhz $m$ mövqedə fərqlənsin.