Computer Science

Vera has N integers a₁, …, a_N. A margin is a nonnegative 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.

Compute the minimum possible margin.

Input Specification

Line 1 contains integers N and K (1 ≤ K ≤ N ≤ 2 · 10⁵).

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

Output Specification

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

Sample Input

1. 5 3
2. 1 -2 10 5 4

download as text file

Output for Sample Input

1. 6

download as text file

Note

For the example, one possible solution is to choose x₁ = –1, x₂ = –2, x₃ = 4, x₄ = 0, x₅ = 0, which is illustrated below: