506. Distance Problem

0

Hard

Rahul enjoys working with arrays and exploring the distances between their elements. This time, he wants to find the k'th smallest distance among all pairs a[i] and a[j], where 0 <= i < j < a.length().
The distance between a pair is defined as the absolute difference between them.

Input Format

The first line of input consists of two integers, N and K, representing the length of the array and the desired k'th smallest distance, respectively.
The second line of input contains N space-separated integers, representing the elements of the array.

Output Format

Output the k'th smallest distance.

Example

Input

3 1
1 3 1

Output

0

Constraints

2 <= n <= 10^4

0 <= nums[i] <= 10^6

1 <= k <= n * (n - 1) / 2

0 <= nums[i] <= 10^6

1 <= k <= n * (n - 1) / 2

Loading...

View Submissions

Console