Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Smallest Interval

By Sherlock221b · Limits 1s, 512 MB

Alice has a collection of N numbers. She would like to place them on a number line. She places each of the N numbers on the point corresponding to its value on the number line. Now she wonders, what’s the size of the smallest interval on the number line such that there are at least K numbers from her collection on that interval?

Input

The first line of the input contains two integers N and K. The next line consists of N space separated integers denoting Alice’s numbers. Let, ai be the ith number on this line.

Constraints:

1 ≤ N ≤ 105

1 ≤ K ≤ N

1 ≤ ai ≤ 109

Output

In a single line, print the size of the smallest interval on the number line where at least K integers from Alice’s collection can be found.

Samples

Input Output
5 3
17 12 5 4 8 
4
Input Output
6 2
16 5 7 4 4 8 
0

Explanation of Sample Case 1: The desired interval is [4,8] which contains 4, 5 and 8. The size of this interval is 4.

Explanation of Sample Case 2: The desired interval is [4,4] which contains 4 and 4. The size of this interval is 0.

Discussion

Statistics


83% Solution Ratio

ArpancseEarliest, May '17

Tarik.amtolyFastest, 0.0s

ArpancseLightest, 524 kB

Tarik.amtolyShortest, 304B

Submit

Login to submit

Related Contests

Tough Cubs' Contest, April 2017 Ended at 2017-05-06 13:30:00 +0000 UTC
BRACU Intra Programming Contest Fall 2018 (Senior) Ended at 2018-09-28 12:30:00 +0000 UTC