---
# System prepended metadata

title: P5

---

# P5
## 題目：Explosionn 與他的ㄌㄌ別墅日常 --- 過河篇
---

## 題目敘述：
今天的天氣十分明朗，於是 Explosionn 打算帶他的ㄌㄌ出去踏青。
不過他們現在遇到了一個問題：前面有一條河
Explosionn 發現河中間有好多個黃金砌成的金磚能讓他的ㄌㄌ過河
Explosionn 因為 Explosionn 都把錢花在ㄌㄌ上，而且吃拉麵都不揪，沒有朋友要幫助他缺錢的窘境
現在他想要把 M 個黃金磚拆起來作為錢錢
但又要考慮到他的ㄌㄌ的步伐並不是很長，現在想要問你在拆除 M 個黃金磚的情況下，金磚與金磚及金磚與河岸之間距離最大值最小可以是多少。
河岸的座標由 0 開始，經由黃金磚的座標，到 L 結束。

---

## 輸入敘述：

第一行有兩個數 L, N, M，分別代表河寬、金磚的數量及要拆除的數量
第二行有 N 個數字 Ni，代表金磚在直線上的座標

1 <= M <= N <= 2*10^5
Ni <= L <= 1e9

給分方式：
40% N,M <= 20
30% N,M <= 1e4
30% 無其他限制

---

## 輸出敘述：

金磚與金磚，金磚與河岸之間距離最大值的最小值

---

```
sample input 1
10 5 2
1 3 5 7 8
sample output 1
3
sample input 2
10 5 2
1 2 3 7 8 10
sample output 2
4
```

---

## HINT

第一題範例測資解釋：
有很多總拆除方法，像是拆除 1, 3 座標的金磚
這樣中間的最大值是 5
但是拆除 1, 7 的方法是最好的，中間最大值是 3

---
