問題
「うう、疲れましたわ・・・」
ステフはそう言い、うとうとしていた。
ステフは今、ある仕事をやらされていた。それは n 個の、城から d 離れた建物の内、 m 箇所に店を配置するという仕事である。というのも、空白兄妹が、国王グッズの店を作ろう、と突然言い出したのが原因である。その上、店の距離が近いとそれぞれの客を取り合ってしまう可能性があるから、全ての店の距離ができる限り遠くなるようによろしく、という注文つきである。
「もうダメですわ・・・」
ついにステフは力尽きた。なのであなたはステフの仕事を引き継ぐことにした。
「たまには自分でやって欲しいですわ・・・」
入力
n m b0 : : : bn-1
1 行目に建物の数を表す整数 n と出店する店舗数を表す整数 m が与えられる。
続く n 行に城から距離の表す b が与えられる。
出力
空白兄妹の出した条件を満たす建物どうしの距離を出力せよ。もし等間隔に配置できない場合は、最小のものを出力せよ。
出力の最後に改行を入れることも忘れずに。
制約
全ての入出力ケースについて以下を満たす。
- 2 ≦ n ≦ 10^5
- 2 ≦ m ≦ n
- 1 ≦ b ≦ 10^9
入出力例
入力例1
5 3 1 4 2 8 9
出力例1
3
入力例2
3 3 1 3 4
出力例2
1