Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

EIUMINDIST - Min Distance

Given an array of N integers, select K elements out of these N elements in such a way that the minimum difference between each of the K numbers is the largest. Your task is to print out the largest minimum difference after choosing any K elements.

Input

-      The first line contains two integers N, K (1  N  105, 2  K  N).

-      The second line contains N integers.

All integers don’t exceed 109

Output

The largest minimum difference after choosing K elements from N elements.

 

Sample

Input

Output

4 3

2 6 2 5

 

1

7 4

1 4 9 0 2 13 3

 

4

 

Note: 50% testcases have K = 2, 3, or 4

 

Explanation

First sample:

  • Select 3 elements 2, 2, 5 will result in minimum difference as 0.
  • Select 2, 5, 6 will result in minimum difference as 6 – 5 = 1 (since 5 – 2 = 3 and 6 – 2 = 4 are not the minimum difference), which is also the largest minimum difference.

Second sample:

  • Select 0, 4, 9, 13 will result in minimum difference of 4, which is the largest minimum difference possible. 

Added by:Ha Minh Ngoc
Date:2022-06-19
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: GOSU
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.