Router Installation

Interview

Time limit2sMemory limit128 MB

Summary

Given house coordinates, place C routers among them to maximize the minimum pairwise distance between chosen routers.

Level: Medium4 of 10
Topics: Binary search, Greedy, Sorting
Solved: No attempts yet

Problem

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.

Input

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).

Output

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

Hint

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.

Examples1

Example 1
Input
```
5 3
1
2
8
4
9
```
Expected output
```
3
```