Aggressive Placement - Classic Problems | Repovive

CLS48. Aggressive Placement

2s256 MB

There are $n$ house positions on a line. Place $k$ routers in distinct houses so that the minimum distance between any two placed routers is as large as possible.

Constraints

$2 \le k \le n \le 2 \cdot 10^5$
$0 \le p_i \le 10^9$
House positions are distinct, but not necessarily given in order.

Input

\begin{array}{l} n \quad k \\ p_1 \quad p_2 \quad \ldots \quad p_n \end{array}

Output

d_{\max}

Samples

Input

5 3
1 2 8 4 9

Explanation

Placing routers at positions 1, 4, and 8 keeps every neighboring gap at least 3; a gap of 4 cannot place all three.

Output

Input

4 2
10 1 20 30

Explanation

Using positions 1 and 30 gives the largest minimum distance, 29.

Output

Input

6 4
0 5 10 15 20 25

Explanation

Four routers can be placed at 0, 5, 15, and 25, so the best minimum distance is 5.

Output

There are $n$ house positions on a line. Place $k$ routers in distinct houses so that the minimum distance between any two placed routers is as large as possible.

$2 \le k \le n \le 2 \cdot 10^5$
$0 \le p_i \le 10^9$
House positions are distinct, but not necessarily given in order.

\begin{array}{l} n \quad k \\ p_1 \quad p_2 \quad \ldots \quad p_n \end{array}

d_{\max}