A corridor has
Each router must be placed at one of the given room positions (a router cannot be placed at an arbitrary point that isn't a room). Every room must be within distance
Find the minimum possible value of
The first line contains two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression — the number of rooms and the number of routers available.
The second line contains KaTeX can only parse string typed expression integers, the positions of the rooms (not necessarily given in sorted order).
Print a single integer — the minimum coverage radius KaTeX can only parse string typed expression needed.
Input
10 2
1 2 3 4 5 6 7 8 9 102Placing one router at room position 3 covers rooms at positions 1 through 5 (radius 2), and a second router at position 8 covers rooms at positions 6 through 10 (radius 2). No smaller radius allows 2 routers to cover all 10 rooms.
Example 2:
Input
4 4
1 5 10 200With exactly as many routers as rooms, each router can be placed directly at its own room, requiring a radius of only 0.
Example 3:
Input
4 1
1 5 10 2010With only 1 router available, it must cover every room from a single position. Placing it at position 10 covers position 1 (distance 9), position 5 (distance 5), position 10 (distance 0), and position 20 (distance 10) — the largest distance from this position is 10, and no other single room position does better.