Waterloo 2017 Fall C - Computer Science

View as PDF

Submit solution

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

Author:
Problem type
2017 Fall Waterloo Local ACM Contest, Problem C

Vera has N integers a1,,aN. A margin is a non-negative integer L such that it is possible to choose N integers x1,,xN such that for all i, 1iN, the interval [xi,xi+L] contains at least K of Vera's integers and also contains ai.

Compute the minimum possible margin.

Input

Line 1 contains integers N and K (1KN2×105).

Line 2 contains N integers, a1,,aN (109ai109).

Output

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

Sample Input

Copy
5 3
1 -2 10 5 4

Sample Output

Copy
6

Note

For the first example, one possible solution is to choose x1=1,x2=2,x3=4,x4=0,x5=0, which is illustrated below.


Comments

There are no comments at the moment.