Sorting the differences - MarisaOJ: Marisa Online Judge

Sorting the differences

Time limit: 1000 ms
Memory limit: 256 MB
Given an array $A$ with $n$ integer elements, rearrange all values of $|A_i - A_j|$ in non decreasing order for all $1 \le i < j \le n$. Determine the value at the $k$-th position in the resulting sequence. ### Input - The first line consists of twos integer $n,k$. - The second line contains $n$ integers $A_i$. ### Output - Print the $k$-th largest value. ### Constraints - $1 \le n \le 10^5$. - $1 \le k \le \frac{n \times (n - 1)}{2}$ - $1 \le A_i \le 10^9$. ### Example Input: ``` 5 9 2 9 4 7 8 ``` Output: ``` 6 ```