Вздовж моря вузькою полоскою тягнеться пляж. У деяких точках пляжу розміщено кіоски з морозивом. В один прекрасний день не усі морозивщики вийшли на роботу. Розподіліть морозивщиків по кіоскам так, щоб мінімальна відстань між морозивщиками було якомога більшою. Так вони менше будуть заважати один одному.
У першому рядку вводяться кількість кіосків n
(2 ≤ n
≤ 10001) та кількість морозивщиків k
(1 ≤ k
≤ n
), які вийшли на роботу. У другому рядку задано n
натуральних чисел у порядку зростання - координати кіосків (координати не перевищують 10^9
).
Виведіть одне число - мінімальну відстань між сусідніми кіосками в оптимальному розміщенні.