Maximum Subset

Interview

Time limit1sMemory limit512 MB

Summary

Given N integers, pick K of them to maximize the smallest gap between any two chosen values; duplicates make the gap zero.

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

Problem

Define the value of a multiset of integers as the minimum difference between any two distinct elements. If a multiset contains two elements with the same value, those two elements are treated as distinct elements, so the value of the multiset is 0.

Given a multiset of integers A with N elements, find the maximum value among the values of subsets of A that consist of K elements.

Input

The first line contains two integers N K (2 ≤ K ≤ N ≤ 100,000). N is the number of elements of A, and K is the number of elements of the subset of A we are looking for. The second line contains N integers A1, A2, ..., AN (0 ≤ Ai ≤ 1,000,000,000), representing the elements of set A.

Output

Output the maximum value among the values of subsets of A that consist of K elements, on one line.

Examples3

Example 1
Input
```
4 2
1 2 4 10
```
Expected output
```
9
```
Example 2
Input
```
4 3
1 2 4 10
```
Expected output
```
3
```
Example 3
Input
```
4 4
1 2 4 10
```
Expected output
```
1
```