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 NN numbers. She would like to place them on a number line. She places each of the NN 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 KK numbers from her collection on that interval?

Input

The first line of the input contains two integers NN (1N1051 \le N \le 10^5) and KK (1KN1 \le K \le N). The next line consists of NN space separated integers denoting Alice's numbers. Let, aia^i (1ai1091 \le a_i \le 10^9) be the ithi^{th} number on this line.

Output

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

Samples

InputOutput
5 3
17 12 5 4 8 
4

The desired interval is [4,8] which contains 4, 5 and 8. The size of this interval is 4.

InputOutput
6 2
16 5 7 4 4 8 
0

The desired interval is [4,4] which contains 4 and 4. The size of this interval is 0.


Discussion

Statistics


85% Solution Ratio

ArpancseEarliest, May '17

Tarik.amtolyFastest, 0.0s

ArpancseLightest, 524 kB

Rafi9998Shortest, 210B

Submit

Login to submit

Editorial

Sort the array in non-decreasing order. Now notice that, the smallest interval that starts at ai and...

Toph uses cookies. By continuing you agree to our Cookie Policy.