003 - 釣り (Fishing)

問題

周の長さが L である湖があります。 この湖の周には、N 箇所の釣り場があって、i 番目の釣り場は、 湖の北端から周に沿って時計回りに X_i 進んだ位置にあります。 あなたはこの湖の周に、K 個の釣具貸出場を設置したいです。

ある設置方法について、「全体の不便さ」は、その設置方法における、すべての釣り場の「不便さ」の最大値と定義されます。 ある釣り場の「不便さ」とは、その釣り場と、そこに最も近い釣具貸出場との間を往復するのにかかる距離です。

「全体の不便さ」を最小化するように釣具貸出場を設置した時の、「全体の不便さ」を求めてください。 なお、釣具貸出場を釣り場と同じ位置に設置しても構いません。

入力

L N K
X1 X2 ... XN

最初の一行には整数 N が与えられる。

続く行には、それぞれの釣り場の位置が与えられる。

出力

「全体の不便さ」の最小値を出力してください。

制約

全ての入出力ケースについて以下を満たす。

• 1 ≦ L ≦ 10⁹
• 1 ≦ N ≦ 10⁵
• 1 ≦ K ≦ N
• 0 ≦ X₁ < X₂ < ... < X_N ≦ 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