問題説明

EVが増え、高速道路の休憩所ごとに充電待ちの列が長くなっています。 ある静かな高速道路に休憩所が一直線に並んでおり、各休憩所は起点(0km)からの距離(km)で与えられます。 予算が厳しいので、充電所はちょうどC個だけ設置できます。 充電所が一箇所に固まると、遠く離れた区間では充電が不便になりますよね？ そこで「最も近い2つの充電所間の距離」が**できるだけ遠くなるように**休憩所を選んで充電所を配置します。 このとき可能な「隣接する充電所間の最小距離」の最大値を求めてください。

入力

出力

制約条件

• •2 ≤ C ≤ N ≤ 200,000
• •0 ≤ 休憩所の位置 ≤ 1,000,000,000（すべて異なる整数）
• •休憩所の位置はソートされていない場合がある

例

6 3
3 6 12 17 25 30

13