BS-M5. Qurbaqa sakrashi

Ariqda bir chiziq bo‘ylab n ta tosh bor, koordinatalari x₁ < x₂ < … < xₙ. Qurbaqa birinchi toshda turibdi va oxirgisiga ko‘pi bilan k ta sakrashda yetib bormoqchi; u faqat toshlarga qo‘nadi va faqat oldinga sakraydi. Eng uzun sakrashi imkon qadar qisqa bo‘lsin — shu uzunlikni toping.

Sakrash uzunligi D dan oshmasa, eng kamida necha sakrash kerakligini ochko‘z usul beradi: har safar D ichidagi eng uzoq toshga sakrash.

Kirish ma’lumotlari

Birinchi qatorda n va k, ikkinchisida n ta koordinata (o‘sish tartibida).

Chiqish ma’lumotlari

Bitta son — eng uzun sakrashning eng kichik qiymati.

Cheklovlar

2 ≤ n ≤ 5·10⁴; 1 ≤ k ≤ n − 1; 0 ≤ xᵢ ≤ 10⁹.