B. Багасгалт

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Танд $n$ ширхэг бүхэл тоон элементтэй $A$ дараалал мөн эерэг бүхэл тоо $k$ байгаа. $A$ дарааллын элементүүд $1$-ээс $n$ хүртэл индекслэгдсэн.

-ийн утга хамгийн бага байхаар та дарааллын элементүүдийн байрыг солих хэрэгтэй байна. Элементийн байрыг солиогүй байхад хамгийн бага байвал та заавал байр солих шаардлагагүй.

Оролт

Эхний мөрөнд хоёр бүхэл тоо $n, k$ ($2 ≤ n ≤ 3*10^{5}$, $1 ≤ k ≤ min(5000, n - 1)$).

Хоёрдох мөрөнд $n$ ширхэг зайгаар тусгаарлагдсан бүхэл тоо $A[1], A[2], ..., A[n]$ ($ - 10^{9} ≤ A[i] ≤ 10^{9}$) -- $A$ дарааллын элементүүд.

Гаралт

Дээрх хамгийн бага болгох шаардлагатай нийлбэрийн хамгийн бага утгыг хэвлэ.

Орчуулсан: Баттулга

Жишээ тэстүүд

Оролт
3 2
1 2 4
Гаралт
1
Оролт
5 2
3 -5 3 -5 3
Гаралт
0
Оролт
6 3
4 3 4 3 2 5
Гаралт
3

Тэмдэглэл

Эхний жишээн дээр тохиромжтой шийдэл нь $1 4 2$ юм.

Хоёрдох жишээн дээр дарааллын хамгийн эхний байрлал нь хамгийн тохиромжтой юм.

Гуравдах жишээн дээр хамгийн тохиромжтой байрлалын нэг нь $2 3 4 4 3 5$ юм.

Сэтгэгдлүүдийг ачааллаж байна...