BS-H3. Qo‘shimcha bekatlar

Avtobus yo‘nalishida n ta bekat bor, koordinatalari x₁ < x₂ < … < xₙ (butun sonlar). Shahar hokimligi yana ko‘pi bilan k ta bekat qurishi mumkin — istalgan butun koordinataga. Qo‘shni bekatlar orasidagi eng katta masofa imkon qadar kichik bo‘lsin. Shu masofani toping.

Bir oraliqni D dan oshmaydigan bo‘laklarga bo‘lish uchun nechta bekat kerakligi oson hisoblanadi.

Kirish ma’lumotlari

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

Chiqish ma’lumotlari

Bitta son — eng katta oraliqning eng kichik qiymati.

Cheklovlar

2 ≤ n ≤ 10⁵; 0 ≤ k ≤ 10⁹; 0 ≤ xᵢ ≤ 10⁹.