Minimize Maximum Distance to Grocery Stores

In a city, there are n households located along a single road and the municipal council plans to open k grocery stores. Each household will choose the nearest grocery store to shop, and the distance it has to travel is the absolute difference between its coordinate and the store's coordinate. The objective is to minimize the maximum distance that any household has to travel.

Formally, given a sorted array of household coordinates ( x_1, x_2, \ldots, x_n ), you need to find the smallest ( d ) such that it is possible to place k stores on the line so that for every household ( x_i ), there is a store placed at some position ( s ) satisfying (|x_i - s| \le d).

A valid approach is to use a binary search on ( d ) combined with a greedy strategy to check if a given ( d ) is feasible.

inputFormat

The first line contains two integers n and k separated by a space, where n is the number of households and k is the number of grocery stores. The second line contains n space-separated integers representing the coordinates of the households.

outputFormat

Output a single integer representing the minimized value of the maximum distance that any household must travel to reach the nearest grocery store.## sample

5 2
1 2 8 4 9

3