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.

Input

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)~.

Output

Print one line with one integer, the minimum possible margin.

Sample Input

5 3
1 -2 10 5 4

Sample Output

6

Note

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.