Computer Science

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 512M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
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.


Comments

There are no comments at the moment.