626. Embarking on the Path of Knighthood

0

Hard

You have been chosen as the squire of a skilled knight who wields two swords simultaneously. In order to become a knight yourself, you must assist him in selecting a pair of swords based on their difference in length.
You will be given the lengths of each sword, and your task is to find the Kth smallest difference between any two swords.
Complete this task promptly to begin your journey towards knighthood.

Input Format

The first line contains two integers K and N (the size of the array).
The second line contains N space-separated integers.

Output Format

Print the Kth smallest difference.

Example

Input

3 1
1 3 1

Output

0

Constraints

- n == nums.length
- 2 <= n <= 1e4
- 0 <= nums[i] <= 1e6
- 1 <= k <= n * (n - 1) / 2

Loading...

View Submissions

Console