Sorting the differences - MarisaOJ: Marisa Online Judge

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$

Topic

Binary search

Rating

1300

Solution (1)

Solution