問題
周の長さが L である湖があります。 この湖の周には、N 箇所の釣り場があって、i 番目の釣り場は、 湖の北端から周に沿って時計回りに Xi 進んだ位置にあります。 あなたはこの湖の周に、K 個の釣具貸出場を設置したいです。
ある設置方法について、「全体の不便さ」は、その設置方法における、すべての釣り場の「不便さ」の最大値と定義されます。 ある釣り場の「不便さ」とは、その釣り場と、そこに最も近い釣具貸出場との間を往復するのにかかる距離です。
「全体の不便さ」を最小化するように釣具貸出場を設置した時の、「全体の不便さ」を求めてください。 なお、釣具貸出場を釣り場と同じ位置に設置しても構いません。
入力
L N K X1 X2 ... XN
最初の一行には整数 N が与えられる。
続く行には、それぞれの釣り場の位置が与えられる。
出力
「全体の不便さ」の最小値を出力してください。
制約
全ての入出力ケースについて以下を満たす。
- 1 ≦ L ≦ 109
- 1 ≦ N ≦ 105
- 1 ≦ K ≦ N
- 0 ≦ X1 < X2 < ... < XN ≦ L-1
小課題
小課題1[25点]
以下の条件を満たす。
- 1 ≦ N ≦ 1000
小課題2[75点]
追加の制約はない。
入出力例
入力例1
10 5 2 1 3 5 7 8
出力例1
3
解説
湖の北端から時計回りに 2 進んだ場所と、6.5 進んだ場所に釣り場貸出場を設置すると、 釣り場 3 ,5 において「不便さ」が 3 になり、 これが最大の「不便さ」なので「全体の不便さ」が 3 になります。 「全体の不便さ」を 3 未満にすることはできないため、3 が答えになります。
入力例2
24 11 3 4 8 9 11 13 17 19 20 21 22 23
出力例2
5