Градња
| време | меморија | улаз | излаз |
|---|---|---|---|
| 0,1 s | 64 Mb | стандардни излаз | стандардни улаз |
За једну дугачку улицу познате су дозвољене локације за градњу. Свака локација је задата по једним целим бројем, растојањем локације од почетка улице. Потребно је изградити \(N\) зграда, али тако да суседне зграде буду што даље једна од друге. Инвеститори оцењују квалитет плана градње \(G\) (то јест избора \(N\) локација) помоћу растојања \(D(G)\). Растојање \(D(G)\) представља најмање растојање између узастопних зграда при плану градње \(G\). Инвеститоре посебно интересује која је највећа могућа вредност \(D(G)\). Напиши програм који за дате дозвољене локације и потребан број кућа исписује највеће растојање које се може постићи.
Улаз
У првом реду дат је број планираних зграда \(N\) (\(2 \leq N \leq L\)), а у другом број расположивих локација \(L\) (\(2 \leq L \leq 10^5\)). У наредних \(L\) редова дати су положаји потенцијалних локација за градњу \(X_i\), (\(1 \leq i \leq L\), \(0 \leq X_i \leq 10^9\)).
Излаз
На стандардни излаз исписати највеће могуће минимално растојање између суседних кућа.
Пример
Улаз
3 7 9 4 6 2 10 14 12
Излаз
5
Објашњење
Дато је 7 локација на којима се граде 3 куће. Ако се оне изграде на локацијама 2, 9 и 14, најмање растојање између кућа је 5 (боље решење од овог није могуће).
Морате бити улоговани како бисте послали задатак на евалуацију.