Relay Network on the Perseus Rift

The Kessarine Concord has spread its outposts along the Perseus Rift, a single hyperspace corridor connecting its worlds. There are $n$ outposts along the Rift, at distinct integer coordinates x_1 < x_2 < \dots < x_n.

To keep in contact across the Rift, the Concord wants to install communication relays at exactly $k$ of these $n$ outposts. Relays installed too close together interfere with each other's signal, so the Concord wants to choose the $k$ outposts so that the smallest distance between any two chosen relays is as large as possible.

Given the outpost coordinates, find the maximum possible value of the minimum distance between any two selected relay outposts.

Input

The first line contains two integers $n$ and $k$ (2 \le k \le n \le 2\cdot10^5) — the number of outposts and the number of relays to install.

The second line contains $n$ integers x_1, x_2, \dots, x_n (0 \le x_i \le 10^9, x_1 < x_2 < \dots < x_n) — the coordinates of the outposts.

Output

Print a single integer — the maximum possible value of the minimum distance between any two chosen relay outposts.

Note

In the first sample, choosing outposts at $1$, $4$ and $8$ gives minimum pairwise distance $3$, which is optimal.