AL04-5. Minoralar

Yo‘l bo‘yida n ta joy bor. Ulardan k tasiga aloqa minorasi qo‘yiladi. Minoralar bir-biriga xalal bermasligi uchun eng yaqin ikki minora orasidagi masofa imkon qadar katta bo‘lsin. Shu masofani toping.

Masofa d berilgan bo‘lsa, «kamida d oraliq bilan k ta minora sig‘adimi?» savoliga ochko‘z usul javob beradi: chapdan yurib, imkon bo‘lishi bilan minora qo‘yamiz. Javobni d bo‘yicha ikkilik qidiruvda toping.

Kirish ma’lumotlari

Birinchi qatorda n va k, ikkinchisida n ta har xil koordinata.

Chiqish ma’lumotlari

Eng kichik masofaning eng katta qiymati.

Cheklovlar

2 ≤ k ≤ n ≤ 10⁵, 0 ≤ xᵢ ≤ 10⁹