Router Installation

There are N houses on a number line. The coordinate of each house is x1, ..., xN, and no two houses share the same coordinate.

Dohyun wants to install C wireless routers so Wi-Fi can be used in as many places as possible. At most one router can be installed in each house. Choose C houses so that the minimum distance between any two installed routers is as large as possible.

Write a program that computes this maximum possible minimum distance.

The first line contains N (2 <= N <= 200,000) and C (2 <= C <= N), separated by one or more spaces. Each of the next N lines contains one house coordinate xi (0 <= xi <= 1,000,000,000).

Print the largest possible distance between the closest pair of installed routers.

Installing routers at 1, 4, and 8, or at 1, 4, and 9, makes the closest pair distance 3. It is impossible to install 3 routers with a larger closest-pair distance.