Vera has N integers a₁, . . . , a_N . A margin is a non-negative integer L such that it is possible to choose N integers x₁, . . . , x_N such that for all i, 1 ≤ i ≤ N, the interval [x_i, x_i + L] contains at least K of Vera’s integers and also contains a_i.</p>

Compute the minimum possible margin.

입력 형식

Line 1 contains integers N and K (1 ≤ K ≤ N ≤ 2 × 10⁵).</p>

Line 2 contains N integers, a₁, . . . , a_N (−10⁹ ≤ a_i ≤ 10⁹).

출력 형식

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

예제 입력

5 3
1 -2 10 5 4

예제 출력

6

힌트

For the first example, one possible solution is to choose x₁ = −1, x₂ = −2, x₃ = 4, x₄ = 0, x₅ = 0, which is illustrated below.</p>