Computer Science

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem type

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.

Sample Input

5 3
1 -2 10 5 4

Sample Output



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.


There are no comments at the moment.