Jelly Swarm
本题没有可用的提交语言。
Description
Jerry the jellyfish wants to join his $N$ friends as they swim around the ocean ($1 \leq N \leq 2*10^5$). Jerry's favorite number is $K$, so he wants to join a swarm of exactly $K$ of his friends ($1 \leq K \leq N$). Each of his friends are located at an integer position of a one-dimensional ocean. More specifically, the $i$th jellyfish is located at position $a_i$. The jellyfish are all located at distinct positions. Jerry prefers tightly packed groups of jellyfish, so he wants to minimize the maximum distance between any two jellyfish in the swarm. Jerry is willing to move anywhere to be with his friends, but unfortunately his friends are too stubborn and will not move. Please help jerry find the maximum distance between any two jellyfish if he chooses a group optimally.
The first line contains two integers $N$ and $K$. ($1 \leq K \leq N \leq 2*10^5$) The next line contains $N$ space-separated integers $a_{1...N}$, where $a_i$ denotes the position of Jerry's $i$th friend. ($1 \leq a_i \leq 10^9$) Note that these positions are distinct.
Output an integer representing the smallest maximum distance between any two jellyfish.
Input
The first line contains two integers $N$ and $K$. ($1 \leq K \leq N \leq 2*10^5$) The next line contains $N$ space-separated integers $a_{1...N}$, where $a_i$ denotes the position of Jerry's $i$th friend. ($1 \leq a_i \leq 10^9$) Note that these positions are distinct.
Output
Output an integer representing the smallest maximum distance between any two jellyfish.
5 3
2 8 6 15 5
7 4
1 2 4 5 6 7 9
3
4
Note
In the first sample, Jerry could chose the group $\{8, 6, 5\}$, and can locate himself at position $7$, making the maximum distance between any two Jellyfish equal to $3$.
In the second sample, even though the group $\{4, 5, 6, 7\}$ has a maximum distance of $3$, Jerry cannot occupy the same space as any of his friends so he must go to either position $3$ or $8$.