Bài 2 : Đèn lồng (6.0 điểm)

Không khí Tết đang rộn ràng khắp mọi nơi. Để chào đón năm mới, các thành viên câu lạc bộ CHTCoder quyết định treo một dãy lồng đèn dọc theo hành lang chính của trường. Hành lang có độ dài \(L\). Ban đầu, các bạn dự định treo \(N\) chiếc đèn lồng tại các vị trí \(a_1, a_2, \dots, a_N\) \((0 < a_1 < a_2 < \dots < a_N < L)\). Hai đầu hành lang (vị trí \(0\) và \(L\)) được xem là hai cột mốc cố định (trên cột mốc đã có đèn lồng).

Tuy nhiên, sau khi treo thử, mọi người nhận thấy mật độ đèn quá dày dẫn đến nhìn rối mắt. Vì vậy, CLB quyết định sẽ tháo bớt tối đa \(M\) chiếc đèn lồng trong số các vị trí dự kiến ban đầu (không thay đổi hai đầu mốc \(0\) và \(L\)).

Yêu cầu: Hãy giúp CHTCoder chọn cách tháo bớt đèn sao cho khoảng cách nhỏ nhất giữa hai chiếc đèn lồng bất kỳ còn lại là lớn nhất có thể, giúp hành lang trở nên thoáng đãng và lung linh nhất.

Input

Vào từ tệp văn bản LANTERN.INP theo cấu trúc:

• Dòng đầu tiên ghi ba số nguyên dương \(L, N, M\) \((1 \le L \le 10^9; 0 \le M \le N \le 10^6)\)
• Dòng thứ hai ghi \(N\) số nguyên \(a_1, a_2, \dots, a_N\) là tọa độ các vị trí dự kiến treo đèn.

Output

Ghi ra tệp văn bản LANTERN.OUT một số nguyên duy nhất là kết quả tìm được.

Example

25 5 2
2 11 14 17 21

4

Scoring

• Có \(40\%\) số test ứng với \(40\%\) số điểm của bài với \(N \le 20\);
• Có \(40\%\) số test ứng với \(40\%\) số điểm của bài với \(M = 0\) và \(N \le 10^6\);
• Có \(20\%\) số test ứng với \(20\%\) số điểm của bài với \(N \le 10^5\);