2017 Fall Waterloo Local ACM Contest, Problem C
Vera has ~N~ integers ~a_1, \dots , a_N~. A margin is a non-negative integer ~L~ such that it is possible to choose ~N~ integers ~x_1, \dots , x_N~ such that for all ~i~, ~1 \le i \le N~, the interval ~[x_i, x_i + L]~ contains at least ~K~ of Vera's integers and also contains ~a_i~.
Compute the minimum possible margin.
Line ~1~ contains integers ~N~ and ~K~ ~(1 \le K \le N \le 2 \times 10^5)~.
Line ~2~ contains ~N~ integers, ~a_1, \dots, a_N~ ~(-10^9 \le a_i \le 10^9)~.
Print one line with one integer, the minimum possible margin.
5 3 1 -2 10 5 4
For the first example, one possible solution is to choose ~x_1 = -1, x_2 = -2, x_3 = 4, x_4 = 0, x_5 = 0~, which is illustrated below.