题目描述

农夫 John 建造了一座很长的畜栏，它包括N $(2 ≤ N ≤ 100,000)$ 个隔间，这些小隔间依次编号为

但是，John的 $C\ (2 ≤ C ≤ N)$ 头牛们并不喜欢这种布局，而且几头牛放在一个隔间里，他们就要发生争斗。为了不让牛互相伤害。John决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的最小距离是什么呢

输入格式

第一行：空格分隔的两个整数N和C；

第二行 到 第 $N+1$ 行： $i+1$ 行指出了 $x_i$ 的位置。

输出格式

一个整数，最大的最小值。

5 3
1
2
8
4
9

3

提示

把牛放在1，4，8这样最小距离是3

数据范围

前$40\%$的数据，$1 \le N,C \le 10^3$

$100\%$的数据，$1\le N,C \le 10^5$