899. Distance Problem

0

Hard

Rahul enjoys working with arrays and exploring their distances. This time, he has a new challenge: finding 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 contains the length of the array, N, and the value of K.
The second line contains 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