404457: GYM101510 C Computer Science

Memory Limit:512 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

C. Computer Sciencetime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

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, 1 ≤ i ≤ N, 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 (1 ≤ K ≤ N ≤ 2 × 105).

Line 2 contains N integers, a1, ..., aN ( - 109 ≤ ai ≤ 109).

Output

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

ExampleInput
5 3
1 -2 10 5 4
Output
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.

加入题单

上一题 下一题 算法标签: